hard Max Points on a Line

Problem Statement

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

Examples

• Example 1:

  • Input: points = [[1,2], [3,6], [5,10], [7,14]]
  • Expected Output: 4
  • Justification: All points lie on the line (y = 2x), forming a straight line with all given points.

• Example 2:

  • Input: points = [[1,1], [2,2], [3,3], [8,10]]
  • Expected Output: 3
  • Justification: The first three points form a line with the equation (y = x), while the fourth point does not lie on this line.

• Example 3:

  • Input: points = [[0,0],[-3,0], [1,1], [2,2], [3, 0], [6, 0]]
  • Expected Output: 4
  • Justification: Points ([1,1]), ([2,2]), and ([0,0]) lie on the line (y = x), making a straight line. The point ([0,0]), (-3, 0), (3, 0), and (6, 0) lie on the x-axis. So, the maximum points on the straight line is 4.

Solution

To solve this problem, we'll leverage the concept of calculating the slope between any two points to determine if they lie on the same line. By iterating over each point and comparing it with every other point, we can calculate the slope and use a hash map to track the number of points that share the same slope with respect to a given point.

This approach ensures we consider every possible line that can be formed with the given points. The key to solving this efficiently lies in accurately calculating and comparing the slopes, taking care of potential issues like vertical lines (where the slope is infinite) and floating-point precision errors. We believe this method is effective because it systematically examines all pairs of points to identify the maximum subset that aligns linearly, thereby ensuring no possible line is overlooked.

Step-by-Step Algorithm

1. Define a Helper Function for GCD: Implement a recursive method gcd to find the greatest common divisor of two numbers. This is crucial for simplifying the slope to its most reduced form, ensuring that slopes are consistently calculated across different pairs of points.

2. Define the Main Function maxPoints:

   • Check if the input points list has fewer than 3 points. If so, return its length, as any two points or a single point always lie on a straight line by definition.

3. Initialize the Maximum Count Variable: Create a variable max_count to keep track of the maximum number of points found on a single line throughout the iteration.

4. Iterate Over Each Point: Use a loop to iterate through each point in the points list. This point will act as a reference point for calculating slopes to every other point.

5. Handle Duplicates and Initialize Local Maximum: For each reference point, initialize duplicate to 1 (to count the reference point itself) and local_max to 0. These variables track the number of duplicate points and the maximum number of points on a line with the same slope, respectively.

6. Create a Slope Map: Initialize a slope_map hashmap to store the count of points that form the same slope with the reference point.

7. Iterate Over Other Points to Calculate Slopes:

   • For each other point, calculate the differences delta_x and delta_y.
   • If both delta_x and delta_y are 0, it means the point is a duplicate of the reference point. Increment duplicate and continue.
   • Calculate the greatest common divisor (GCD) of delta_x and delta_y, and reduce them by this GCD to get the simplest form of the slope.
   • Convert the slope to a string format "{delta_y}/{delta_x}" and use it as a key in slope_map to count how many points share this slope.

8. Update Local and Global Maximums: After checking all points against the current reference point, update local_max to reflect the highest number of points on a line for the current slope. Then, update max_count with the greater of its current value or local_max + duplicate.

9. Return the Maximum Count: After iterating through all points, return max_count as the solution.

Algorithm Walkthrough

Let's consider the Input: points = [[0,0],[-3,0], [1,1], [2,2], [3, 0], [6, 0]].

• Initialization: max_count is set to 0.

• First Iteration (Reference Point [0,0]):

  • duplicate is 1. slope_map is empty: {}.
  • Compare with [-3,0]: delta_x = -3, delta_y = 0,Gcd(-3, 0) = -3, slope is "(0/-3)/(-3/-3)". slope_map becomes {"0/1": 1}.
  • Compare with [1,1]: delta_x = 1, delta_y = 1, slope is "1/1". slope_map becomes {"0/2": 1, "1/1": 1}.
  • Compare with [2,2]: delta_x = 2, delta_y = 2, slope is "1/1" (after reduction). slope_map updates to {"0/-3": 1, "1/1": 2}.
  • Compare with [3,0]: delta_x = 3, delta_y = 0,Gcd(3, 0) = -3, slope is "(0/3)/(3/3)". so slope_map updates to {"0/1": 2, "1/1": 2}.
  • Compare with [6,0]: delta_x = 6, delta_y = 0,Gcd(6, 0) = 6, slope is "(0/6)/(6/6)". so slope_map becomes {"0/1": 3, "1/1": 2}.
  • local_max is 3 for the slope "0/-3", adding duplicate (1), max_count becomes 4.

• Second Iteration (Reference Point [-3,0]):

  • Initialization: For this iteration, duplicate is again set to 1, and slope_map is reset to empty: {}.

  • Compare with [1,1]:

    • delta_x = 4 (1 - (-3)), delta_y = 1 (1 - 0).
    • gcd(4, 1) = 1, so the slope remains "1/4".
    • Update slope_map to {"1/4": 1}.

  • Compare with [2,2]:

    • delta_x = 5, delta_y = 2.
    • gcd(5, 2) = 1, slope simplifies to "2/5".
    • Update slope_map to {"1/4": 1, "2/5": 1}.

  • Compare with [3,0]:

    • delta_x = 6, delta_y = 0.
    • gcd(6, 0) = 6, resulting in the simplified slope "0/1".
    • Update slope_map to {"0/1": 1, "1/4": 1, "2/5": 1}.

  • Compare with [6,0]:

    • delta_x = 9, delta_y = 0.
    • gcd(9, 0) = 9, slope simplifies to "0/1".
    • Update slope_map to {"0/1": 2, "1/4": 1, "2/5": 1}.

• Determine local_max for this iteration:

  • The highest count in slope_map is for the slope "0/1", which is 2. Since duplicate is 1, and considering this iteration does not add any new points to the line (duplicates were handled in the first iteration), local_max is 2.

• Update max_count:

  • The global max_count remains 4 from the first iteration, as local_max + duplicate (2 + 1) does not exceed the current max_count.

• Subsequent Iterations: Repeat the process for each point as the reference point. However, the first iteration already found the maximum count of 4, which matches the maximum possible for any line in this set of points.

• Conclusion: The function returns max_count = 4, which is the maximum number of points on a straight line in the given list of points.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {

  private int gcd(int a, int b) {
    // Base case for the recursive GCD (Greatest Common Divisor) function
    if (b == 0) return a;
    // Recursive call to find the GCD
    return gcd(b, a % b);
  }

  public int maxPoints(int[][] points) {
    if (points.length < 3) return points.length;
    int max = 0;
    // Iterate over all points to use each as a starting point
    for (int i = 0; i < points.length; i++) {
      int duplicate = 1; // Count the point itself
      int localMax = 0;
      Map<String, Integer> map = new HashMap<>();
      // Compare with all other points to find lines
      for (int j = i + 1; j < points.length; j++) {
        int deltaX = points[j][0] - points[i][0];
        int deltaY = points[j][1] - points[i][1];
        if (deltaX == 0 && deltaY == 0) {
          // Count duplicate points
          duplicate++;
          continue;
        }
        int gcd = gcd(deltaX, deltaY);
        // Reduce the deltaX and deltaY by their greatest common divisor
        deltaX /= gcd;
        deltaY /= gcd;
        String slope = deltaY + "/" + deltaX;
        // Increment count of points with this slope
        map.put(slope, map.getOrDefault(slope, 0) + 1);
        localMax = Math.max(localMax, map.get(slope));
      }
      max = Math.max(max, localMax + duplicate);
    }
    return max;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    int[][] example1 = { { 1, 2 }, { 3, 6 }, { 5, 10 }, { 7, 14 } };
    System.out.println(
      "Example 1 Expected Output: 4, Actual Output: " +
      solution.maxPoints(example1)
    );

    // Example 2
    int[][] example2 = { { 1, 1 }, { 2, 2 }, { 3, 3 }, { 8, 10 } };
    System.out.println(
      "Example 2 Expected Output: 3, Actual Output: " +
      solution.maxPoints(example2)
    );

    // Example 3
    int[][] example3 = {
      { 0, 0 },
      { -3, 0 },
      { 1, 1 },
      { 2, 2 },
      { 3, 0 },
      { 6, 0 },
    };
    System.out.println(
      "Example 3 Expected Output: 4, Actual Output: " +
      solution.maxPoints(example3)
    );
  }
}

Complexity Analysis

Time Complexity

The time complexity of the solution is . This arises because for each point, we compare it to every other point, leading to an complexity. Within this nested loop, we calculate the Greatest Common Divisor (GCD) for the slope, which can be done in time using the Euclidean algorithm, where (n) is the maximum value of the coordinates. Thus, the total time complexity becomes .

Space Complexity

The space complexity is . The primary extra space usage comes from the hash map used to store the slopes and their counts for each point considered as a starting point. In the worst case, the hash map could have an entry for every other point in the dataset if no two points form a line with the same slope, thus leading to space usage.