Sometimes, while in competitive programming, we might be facing a problem which is of geometry domain and works with x-y coordinate system. The list of tuple can be used to store the same. And along with this, there might be a problem in which we need point with max value of x axis with similar y axis i.e farthest point on horizontal lines. Let’s discuss certain ways to discuss this problem.
Method : Using list comprehension + max() This is a generic brute force method applied to get the max x axis point for common y axis, made as 1 liner using list comprehension. The max() is used to find the max of x axis element.
Python3
# Python3 code to demonstrate working of# Farthest point on horizontal lines in 2D plane# Using list comprehension + max()from collections import defaultdict# initializing listtest_list = [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)]# printing original listprint("The original list is : " + str(test_list))# Using list comprehension + max()# Farthest point on horizontal lines in 2D planetemp = defaultdict(list)for key, val in test_list: temp[val].append(key)res = [(key, val) for key, val in test_list if max(temp[val]) == key]# Printing resultprint("The list after filtering just maximum points on lines : " + str(res)) |
The original list is : [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)] The list after filtering just maximum points on lines : [(4, 6), (6, 8), (2, 9)]
Time Complexity: O(n*n) where n is the number of elements in the list “res_list”.
Auxiliary Space: O(n), where n is the number of elements in the new res list
Method#2 : Using dictionary
To find the farthest point on horizontal lines in a 2D plane, we can first group the points by their y-coordinate and then find the point with the maximum x-coordinate for each group. This is because the farthest point on a horizontal line is the one that is furthest to the right.
Python3
original_list = [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)]# Group the points by their y-coordinategroups = {}for point in original_list: x, y = point if y not in groups: groups[y] = [point] else: groups[y].append(point)# Find the point with the maximum x-coordinate for each groupfiltered_list = []for group in groups.values(): max_x = max(point[0] for point in group) filtered_list.append((max_x, group[0][1]))# Print the original list and the filtered listprint("The original list is :", original_list)print("The list after filtering just maximum points on lines :", filtered_list) |
The original list is : [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)] The list after filtering just maximum points on lines : [(4, 6), (6, 8), (2, 9)]
Time complexity: O(N log N)
Auxiliary Space: O(N)
Method#3: Using the itertools.groupby() function :
Algorithm:
1.Sort the list of points based on their y-coordinate using the sorted() function and a lambda function that extracts the y-coordinate.
2.Group the sorted list by y-coordinate using the itertools.groupby() function.
Iterate through the groups and for each group:
3.Extract the list of points in the group.
4.Find the farthest point on that group using the max() function and a lambda function that extracts the x-coordinate.
5.Append the farthest point on each group to a list called farthest_points.
6.Print the farthest_points list.
Python3
import itertools# initializing listtest_list = [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)]# printing original listprint("The original list is : " + str(test_list))# Using itertools.groupby() function# Farthest point on horizontal lines in 2D planegroups = itertools.groupby(sorted(test_list, key=lambda p: p[1]), key=lambda p: p[1])farthest_points = []for _, group in groups: points = list(group) farthest_x = max(points, key=lambda p: p[0])[0] farthest_points.append((farthest_x, points[0][1]))# Printing resultprint("The farthest points on horizontal lines are : " + str(farthest_points))#This code is contributed by Jyothi pinjala. |
The original list is : [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)] The farthest points on horizontal lines are : [(4, 6), (6, 8), (2, 9)]
Time complexity:
The sorting operation in step 1 takes O(n log n) time, where n is the number of points in the input list.
The itertools.groupby() function in step 2 takes O(n) time.
The iteration through the groups in step 3 takes O(k) time, where k is the number of unique y-coordinates in the input list.
The finding of the farthest point in each group in step 3.2 takes O(m) time, where m is the number of points in the group with the largest number of points.
Therefore, the overall time complexity of this algorithm is O(n log n + k * m).
Auxiliary Space:
The sorting operation in step 1 requires O(n) additional space to store the sorted list.
The itertools.groupby() function in step 2 requires O(n) additional space to store the groups.
The farthest_points list in step 3.3 requires O(k) additional space to store the farthest points.
Therefore, the overall space complexity of this algorithm is O(n).
