Python | Farthest point on horizontal lines in 2D plane

0 0 3 minutes read

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 list
test_list = [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)]
 
# printing original list
print("The original list is : " +  str(test_list))
 
# Using list comprehension + max()
# Farthest point on horizontal lines in 2D plane
temp = 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 result
print("The list after filtering just maximum points on lines : " +  str(res))

Output :

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-coordinate
groups = {}
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 group
filtered_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 list
print("The original list is :", original_list)
print("The list after filtering just maximum points on lines :", filtered_list)

Output

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 list
test_list = [(1, 6), (4, 6), (2, 6), (6, 8), (1, 8), (2, 9)]
 
# printing original list
print("The original list is : " + str(test_list))
 
# Using itertools.groupby() function
# Farthest point on horizontal lines in 2D plane
groups = 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 result
print("The farthest points on horizontal lines are : " + str(farthest_points))
#This code is contributed by Jyothi pinjala.

Output

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).