0149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line

Description

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.

ac

GCD calculation

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        // edge case
        if (points == null || points.length == 0) return 0;
        if (points.length <= 2) return points.length;


        int res = 0;
        for (int i = 0; i < points.length; i++) {
            HashMap<String, Integer> map = new HashMap<>();
            int samePoint = 0;
            int sameXAxis = 1;
            // 3 scenarios: 1) samepoint; 2) in the same x axis; 3) has same slope
            for (int j = 0; j < points.length; j++) {
                // if (i == j) continue;
                if (i != j) {
                    // same point
                if (points[i].x == points[j].x && points[i].y == points[j].y) samePoint++;
                // same x axis
                if (points[i].x == points[j].x) {
                    sameXAxis++;
                    continue; // cannot calculate slope, continue
                }
                // slope
                int numerator = points[i].y - points[j].y;
                int denominator = points[i].x - points[j].x;
                int gcd = gcd(numerator, denominator);
                String hashStr = (numerator / gcd) + "/" + (denominator / gcd);
                map.put(hashStr, map.getOrDefault(hashStr, 1) + 1); // 2 points in same slope
                res = Math.max(res, map.get(hashStr) + samePoint);
                }

            }
            res = Math.max(res, sameXAxis);
        }

        return res;
    }

    private int gcd(int a, int b) {
        if(a == 0) return b;
        return gcd(b % a, a);
    }
}