LeetCode Solution: Max Points on a Line

 Question: 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.

Constraints:

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

Solution: 

To solve this problem, you can iterate through each point in the array and check how many other points lie on the same straight line with it. You can do this by calculating the slope between the two points and checking if the slope is the same for all other points.

import java.util.HashMap;

import java.util.Map;

class Solution {

    public int maxPoints(int[][] points) {

        int maxPoints = 0;

        for (int i = 0; i < points.length; i++) {

            int samePoints = 1;

            Map<String, Integer> slopeCount = new HashMap<>();

            for (int j = 0; j < points.length; j++) {

                if (i == j) {

                    continue;

                }

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

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

                if (dx == 0 && dy == 0) {

                    samePoints++;

                    continue;

                }

                int gcd = gcd(dx, dy);

                String slope = (dy / gcd) + "/" + (dx / gcd);

                slopeCount.put(slope, slopeCount.getOrDefault(slope, 1) + 1);

            }

            int sameSlopePoints = samePoints;

            for (int count : slopeCount.values()) {

                sameSlopePoints = Math.max(sameSlopePoints, count);

            }

            maxPoints = Math.max(maxPoints, sameSlopePoints);

        }

        return maxPoints;

    }

    private static int gcd(int a, int b) {

        if (b == 0) {

            return a;

        }

        return gcd(b, a % b);

    }

}