LeetCode Hard – Max Points on a Line

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 1:

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

Output: 3

Example 2:

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

Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Java Solution

To solve this problem, you can iterate through each pair of points and calculate the slope of the line formed by those points. Keep track of the slopes in a map for each point, and count the number of points with the same slope. The maximum count will give you the maximum number of points lying on the same straight line.

Here’s the Java solution:

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

public class MaxPointsOnLine {
    public int maxPoints(int[][] points) {
        if (points.length <= 1) {
            return points.length;
        }

        int maxPoints = 1;

        for (int i = 0; i < points.length; i++) {
            Map<Double, Integer> slopeCount = new HashMap<>();
            int duplicate = 0;
            int vertical = 0;
            int localMax = 1;

            for (int j = i + 1; j < points.length; j++) {
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];

                if (x1 == x2 && y1 == y2) {
                    duplicate++;
                } else if (x1 == x2) {
                    vertical++;
                    localMax = Math.max(localMax, vertical + 1);
                } else {
                    double slope = 1.0 * (y2 - y1) / (x2 - x1);
                    slopeCount.put(slope, slopeCount.getOrDefault(slope, 1) + 1);
                    localMax = Math.max(localMax, slopeCount.get(slope));
                }
            }

            maxPoints = Math.max(maxPoints, localMax + duplicate);
        }

        return maxPoints;
    }

    public static void main(String[] args) {
        MaxPointsOnLine solution = new MaxPointsOnLine();

        // Example 1
        int[][] points1 = {{1, 1}, {2, 2}, {3, 3}};
        System.out.println(solution.maxPoints(points1));  // Output: 3

        // Example 2
        int[][] points2 = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
        System.out.println(solution.maxPoints(points2));  // Output: 4
    }
}

This Java code defines a MaxPointsOnLine class with the maxPoints method, which calculates the maximum number of points lying on the same straight line. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for finding the maximum number of points that lie on the same straight line:

from collections import defaultdict

class MaxPointsOnLine:
    def maxPoints(self, points):
        if len(points) <= 1:
            return len(points)

        max_points = 1

        for i in range(len(points)):
            slope_count = defaultdict(int)
            duplicate = 0
            vertical = 0
            local_max = 1

            for j in range(i + 1, len(points)):
                x1, y1 = points[i]
                x2, y2 = points[j]

                if x1 == x2 and y1 == y2:
                    duplicate += 1
                elif x1 == x2:
                    vertical += 1
                    local_max = max(local_max, vertical + 1)
                else:
                    slope = (y2 - y1) / (x2 - x1)
                    slope_count[slope] += 1
                    local_max = max(local_max, slope_count[slope])

            max_points = max(max_points, local_max + duplicate)

        return max_points

# Test cases
solution = MaxPointsOnLine()

# Example 1
points1 = [[1, 1], [2, 2], [3, 3]]
print(solution.maxPoints(points1))  # Output: 3

# Example 2
points2 = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
print(solution.maxPoints(points2))  # Output: 4

This Python code defines a MaxPointsOnLine class with the maxPoints method, which calculates the maximum number of points lying on the same straight line. The provided test cases demonstrate its usage.