Problem

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

OR

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example

Example 1:

1
2
3
4

Input:
points = [[1,1],[2,2],[3,3]]
Output:
 3

Example 2:

1
2
3
4

Input:
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output:
 4

Input Format

Either assume points as input OR You will be give 2 arrays X and Y. Each point is represented by (X[i], Y[i]) OR we can use Point class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Point {
	int x;
	int y;
	Point() {
		this(0,0);
	}
	Point(int a, int b) {
		x = a;
		y = b;
	}
}

To convert int[][] points to Point[] points:

1
2
3
4
5

Point[] pointsArr = new Point[points.length];
int i = 0;
for(int[] point: points){
	pointsArr[i++] = new Point(point[0], point[1]);
}

Solution

Method 1 - Check the Slope

The equation of a line is expressed as y = mx + c, where y and x are variables, and m and c represent the slope and y-intercept respectively.

To solve this problem, one can count the number of points sharing the same slope relative to each starting point. Special cases such as duplicate points and vertical lines require careful handling. For vertical lines, the slope is undefined, but they can be assigned a distinct representation like infinity.

The slope can be calculated as m = (y2 - y1) / (x2 - x1), which results in a double value. However, using doubles as keys in a HashMap can be problematic due to precision concerns.

Handling Double as Key in Map

While it is generally not ideal to use doubles as keys, it is acceptable in this problem if edge cases involving gradient 0.0 are managed correctly. Double values treat +0.0 and -0.0 as distinct keys, which avoids conflicts. Here is a key example:

1

double m =  (p2.y == p1.y) ? 0.0 : ((double) (p2.y - p1.y) / (p2.x - p1.x));

Despite this workaround, large numbers risk hitting limitations in double precision, which can lead to overflow and inaccuracies.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n < 2) return n;
        
        int ans = 0;

        for (int i = 0; i < n; i++) {
            HashMap<Double, Integer> slopeCount = new HashMap<>();
            int duplicate = 0;
            int max = 0;

            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    duplicate++;
                    continue;
                }

                // Calculate the slope as a double (dy/dx)
                double slope = dx == 0 ? Double.POSITIVE_INFINITY : (double) dy / dx;

                slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
                max = Math.max(max, slopeCount.get(slope));
            }
            ans = Math.max(ans, max + duplicate + 1); // Include duplicates and the current point
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n < 2:
            return n

        ans = 0

        for i in range(n):
            slope_count: defaultdict[float, int] = defaultdict(int)
            duplicate = 0
            max_pts = 0

            for j in range(n):
                if i == j:
                    continue

                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]

                if dx == 0 and dy == 0:
                    duplicate += 1
                    continue
                
                # Calculate the slope as dy / dx using float precision
                slope = float('inf') if dx == 0 else dy / dx
                slope_count[slope] += 1
                max_pts = max(max_pts, slope_count[slope])
            
            ans = max(ans, max_pts + duplicate + 1)  # Including duplicates and the current point

        return ans

Complexity

  • ⏰ Time complexity: O(n^2), as calculating slopes for all pairwise combinations gives O(n^2).
  • 🧺 Space complexity: O(n)

Method 2 - Use Pairing Function and GCD

The problem is to determine the maximum number of points that lie on the same straight line. To achieve this:

  1. Basic Geometry: Any two points define a straight line. If we compute slopes of lines formed by a pair of points, we can group points with the same slope to determine the maximum collinear set of points.
  2. Handling Precision: Since slopes can be represented as a fraction (dy/dx), we should ensure precision by using the greatest common divisor (GCD) to simplify the fraction.
  3. Algorithm:
    • Iterate through each point in the array.
    • Calculate the slope of lines formed with every other point in the array.
    • Store slopes in a hashmap to count occurrences of each slope.
    • For each iteration of the outer loop, track the maximum count of collinear points (including the point itself).

This approach is slower compared to the standard solution that uses doubles for storing slopes. However, it ensures complete precision when working with integer coordinates.

A pairing function can uniquely represent a pair of integers, as explained here: https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function. In this method, the pairing function is used to encode a fraction by treating the numerator and denominator as a unique pair of integers, thus eliminating potential precision issues associated with using floats or doubles.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Solution {
    public int maxPoints(int[][] points) {
        int ans = 0;
        int n = points.length;

        for (int i = 0; i < n; i++) {
            HashMap<String, Integer> slopeCount = new HashMap<>();
            int duplicate = 0, max = 0;

            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    duplicate++;
                    continue;
                }

                // Simplify slope using GCD
                int gcd = gcd(dx, dy);
                dx /= gcd;
                dy /= gcd;

                String slope = dy + "/" + dx; // Represent slope as string to handle precision
                slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
                max = Math.max(max, slopeCount.get(slope));
            }
            ans = Math.max(ans, max + duplicate + 1); // Include duplicates and the current point
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 0

        for i in range(n):
            slope_count: defaultdict[str, int] = defaultdict(int)
            duplicate = 0
            max_pts = 0

            for j in range(i + 1, n):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]

                if dx == 0 and dy == 0:
                    duplicate += 1
                    continue

                # Simplify the slope using GCD
                g = gcd(dx, dy)
                dx //= g
                dy //= g

                slope = f"{dy}/{dx}"  # Represent the slope as a string to handle precision
                slope_count[slope] += 1
                max_pts = max(max_pts, slope_count[slope])
            
            ans = max(ans, max_pts + duplicate + 1)  # Including duplicates and the current point

        return ans

Complexity

  • ⏰ Time complexity: O(n^2). Outer loop iterates n times and computes slopes with the remaining points, costing O(n^2) time.
  • 🧺 Space complexity: O(n). The hashmap used to store slopes can have O(n) space at maximum.