Max Points On A Line - Leetcode Solution

The problem “Max Points on a Line” on LeetCode asks us to find the maximum number of points that are located on the same line given an array of points.

Approach: We can use a hashmap to store the slope of the line between each point and count the maximum number of points on the same line.

Algorithm:

1. Create a hashmap named as slopes, which will store the slope(value) of each point(key) in the given points array.

2. Iterate through each point in the given points array.

3. Initialize two counters, one for the duplicate points and the other for the maximum number of points on the same line containing the current point.

4. For each point, iterate through the remaining points in the array and calculate the slope of the line passing through the current point and the remaining point.

5. If the current point is same as the remaining point, then increment the duplicate points counter.

6. If the slope does not exist in the hashmap, then add it along with the count 2 (the current point and the remaining point).

7. If the slope already exists in the hashmap, then increment its count by 1.

8. Update the maximum number of points by comparing the current number of points with the maximum number of points so far.

9. Repeat steps 4-8 for each point in the given array.

10. Return the maximum number of points on the same line.

Code:

Here is the Java implementation of the above algorithm:

class Solution { public int maxPoints(int[][] points) { if (points.length == 0) return 0; int maxPoints = 1; for(int i = 0; i < points.length; i++){ Map<Double, Integer> slopes = new HashMap<>(); int count = 1; for(int j = i+1; j < points.length; j++){ int x1 = points[i][0]; int x2 = points[j][0]; int y1 = points[i][1]; int y2 = points[j][1]; if (x1 == x2 && y1 == y2) { count++; continue; } double k = (x1 == x2) ? Double.POSITIVE_INFINITY : ((double) (y2-y1) / (double) (x2-x1)); if (slopes.containsKey(k)) { slopes.put(k, slopes.get(k)+1); } else { slopes.put(k, 2); } } if (slopes.isEmpty()) { maxPoints = Math.max(maxPoints, count); } else { for (int value: slopes.values()) { maxPoints = Math.max(maxPoints, count+value-1); } } } return maxPoints; } }

Time Complexity: O(n^2) - As we need to traverse all the points and for each point, we need to traverse the remaining points.

Space Complexity: O(n) - As we are using a hashmap of space proportional to the number of points in the given array.

1