Max Points On The Straight Line

Max points on the straight line

Difficulty: Hard

Asked in: Amazon, Google

Understanding the Problem

Problem Description

Given N point on a 2D plane as pair of (x, y) coordinates, Write a program to find the maximum number of point which lie on the same line.

Example 1

Input: A[][] = [[1,1],[2,2],[1,2],[3,3],[2,3]]
Output: 3
Explanation: The maximum number of point which lie on same line are 3, those points are [1,1], [2, 2] and [3, 3]

Example 2

Input: A[][] = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: The maximum number of point which lie on same line are 4, those points are [3,2], [4,1], [2,3] and [1, 4].

Solutions

We will be discussing two different ways to solve this problem

Brute Force — For every pair of points, check how many other points are collinear with them and maintain track of it.
Using Map — For every point, maintain a hashmap for the slope of that point to every other point, and maintain the max_pts count.

You may try this problem here .

1. Brute Force

To compute the number of points on a line, we need to

We need to take two points and check if all other points are collinear with those two points.
We need to keep track of the number of points that are collinear with the two points as we have been asked the maximum number of points lying on a straight line.
We also need to keep in mind the case when two points could coincide. If the two points coincide, then there could be many lines based on two coinciding points.

Solution Steps

For every pair of non-coinciding points, check how many other points are collinear with those two points.
Maintain a max_pts that will store the maximum number of points that will be lying on the same line.

Pseudo Code

// check whether the three points are on the same line
int coline(int[] a,int[] b,int[] c){ 
    if (a[0]-c[0])*(b[1]-c[1]) == (a[1]-c[1])*(b[0]-c[0])
        return 1
    else
        return 0
}
int maxPoints(int[][] points) {
    int n = points.size()
    int max_pts = 0
    for(int i = 0 to i < n){
        for(int j = i+1 to j < n){
            if(points[i][0]==points[j][0] && points[i][1]==points[j][1]) 
                continue
            int sum = 0
            for(int k = 0 to k < n) 
                sum += coline(points[i],points[j],points[k])
            max_pts = max(max_pts,sum)
        }
    }
    if(max_pts==0)
        return n
    else
        return max_pts
}

Complexity Analysis

Time Complexity: O(n³)

Space Complexity: O(1)

Critical Ideas to Think

We took two points and calculated its slope and then look for every other point with the same slope and thus maintained the counter. But a unique line is determined both by the slope and intercept. How did we manage to maintain a counter for each slope without checking for intercept?
How did we ensure that this solution is correct even for overlapping points?
What does coline function represent?

2. Using Map

A line passing through two points has a unique slope. One could deduce that if we take a point p1 from the set of points and draw lines from p1 to all other points, then each of them will give a slope and if there are same slopes for multiple points, then definitely, the points with the same slope will be on the same line or you can say collinear. So, if you will think about it, when we pick points one by one from the set of points and find slopes for every other point, we removed the possibility of parallel lines for each iteration. Thus, maintaining a hash map of slope will help us identify the maximum number of points lying on the same line.

Solution Steps

For each point, find the slope from that point to every other point.
Create an ordered-map and store the total number of collinear points against the slope.
To find the slope, use the formula (x2 — x1) / (y2 — y1) . Use double instead of float to maintain the precision level.
To manage the edge cases, Create an overlap variable to check for repeating points and create a vertical variable to count the number of points lying on the line parallel to the Y-axis.
Lastly, maintain a res to store the maximum number of points lying on the same line.

Pseudo Code

int maxPoints(int[][] points) {
    int max_pts = 0
    for (int i = 0 to i < points.size()) {
        int localmax = 0, overlap = 1, vertical = 1;
        map<double, int> m
        for (int j = i + 1 to j < points.size()) {
            if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) 
                overlap = overlap + 1
            else 
                if (points[i][0] == points[j][0]) 
                vertical = vertical + 1
            else {
                slope = double(points[i][1] - points[j][1]) / (points[i][0] - points[j][0])
                m[slope] = m[slope] + 1
            }
        }
        for (slope in m)
            localmax = max(m[slope], localmax)
        max_pts = max(vertical, max(localmax + overlap, max_pts))
    }
    return max_pts
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n)

Critical Ideas to Think

Why did we create a map to store the slope for each point?
How did we maintain the precision of slope for large numbers?
How did we manage for infinity slope and overlapping points in the above approach?
We took a point A and tried to find the slope for the lines starting from A to every other point B and stored into a map. A unique line is determined both by the slope and intercept. How did we manage to maintain a counter for each slope without checking for intercept?