149. Max Points on a Line - Detailed Explanation

Problem Statement

You are given an array of points where each point is represented as a pair of integers ([x, y]) that denotes its coordinates on the 2D plane. Your task is to determine the maximum number of points that lie on the same straight line.

Example 1
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation: All three points lie on the line (y = x).

Example 2
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: One of the lines that gives the maximum number of points is through the points ([1,1]), ([3,2]), ([5,3]), and ([2,3]) (when correctly computed with slope consistency).

Example 3
Input: [[0,0],[0,0],[1,1]]
Output: 3
Explanation: Even though the point ([0,0]) appears twice, both occurrences count, and together with ([1,1]), they all lie on the line (y = x).

Constraints:

• (1 \leq \text{points.length} \leq 300)
• (\text{points}[i].\text{length} == 2)
• (-10^4 \leq x_i, y_i \leq 10^4)

Hints

1. Handling Slopes: When considering the line between two points, the slope (i.e., the ratio of the difference in y-coordinates to the difference in x-coordinates) is key. However, watch out for division by zero when the line is vertical.

2. Using a HashMap: For each point, you can compute the slope it makes with every other point and use a hash map (or dictionary) to count how many points share the same slope relative to that point. This helps in quickly finding the maximum collinear points.

Approach 1: Brute Force

Explanation

A brute force solution involves checking every possible pair of points, determining the line they form, and then counting how many other points lie on that same line. For every pair ((i, j)), you would:

• Compute the line’s slope and intercept.
• Count how many points satisfy the equation of the line.
• Track the maximum count found.

While this approach is straightforward, its time complexity is (O(n^3)) (where (n) is the number of points) because for every pair of points, you scan the entire list. This makes it impractical for larger inputs.

Step-by-Step Walkthrough (Brute Force)

1. Pair Selection: For each point (i), iterate through every other point (j) to form a candidate line.

2. Line Equation: Calculate the slope (and intercept, if needed) for the line through points (i) and (j).

   • Handle vertical lines separately (where (x_i == x_j)).

3. Counting Points: For the candidate line, iterate through all points to check if they satisfy the line equation.

4. Update Maximum: Keep track of the maximum number of collinear points found.

Complexity Analysis (Brute Force)

• Time Complexity: (O(n^3)) – three nested loops (pair selection and then a full scan to count points).
• Space Complexity: (O(1)) – aside from the input storage, only a few auxiliary variables are used.

Note: Due to its inefficiency, the brute force method is usually not the best choice for inputs with larger (n).

Approach 2: Optimal HashMap-Based Solution

Explanation

A more efficient approach leverages the idea of fixing one point and calculating the slope it makes with every other point, using a hash map (or dictionary) to count occurrences of each slope. The key observations are:

• Duplicate Points: They should be counted separately.

• Normalization: To avoid floating-point precision issues, compute the greatest common divisor (GCD) of the differences and normalize the slope to its reduced form.

• Vertical Lines: They can be handled by a unique representation (e.g., using a tuple that indicates an infinite slope or by treating the x-difference as zero and using the absolute value of the y-difference).

Step-by-Step Walkthrough (Optimal Approach)

1. Iterate Through Points: For each point (i), create a new hash map to record slopes.

2. Calculate Slope for Each Pair:

   • For each point (j) ((j > i)), calculate (\Delta x) and (\Delta y).
   • If both differences are zero, increment the duplicate count.
   • Otherwise, compute the GCD of (\Delta x) and (\Delta y) and divide both by the GCD to normalize the slope.
   • Normalize the sign (e.g., ensure the x-difference is positive).

3. Count Occurrences: Use the normalized slope as the key in the hash map and increment its count.

4. Update Local Maximum: The maximum number of points on a line with point (i) is the maximum value in the hash map plus the duplicate count plus one (for the point (i) itself).

5. Global Maximum: Track and update the overall maximum across all iterations.

Complexity Analysis (Optimal Approach)

• Time Complexity: (O(n^2)) – for each point, you iterate through all other points.

• Space Complexity: (O(n)) – due to the hash map used to store slopes for each point.

Code Implementations

Python Code