149-max-points-on-a-line

Question

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

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example:

Thought Process

1. Brute Force - HashMap
   1. We simply create all possible pair of points, and calculate their slope and intercept
   2. Use the string representation of slope
   3. Time complexity O(n^2)
   4. Space complexity O(n^2)

Solution

/**
 * 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) {
        if (points.length <= 2) return points.length;
        int n = points.length;
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            int sameP = 0, max = 0;
            Map<String, Integer> map = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                int x = points[i].x - points[j].x;
                int y = points[i].y - points[j].y;
                if (x == 0 && y == 0) {
                    sameP++;
                    continue;
                }
                // divide by gcd to reduce the factor in slope
                int gcd = gcd(x, y);
                x /= gcd;
                y /= gcd;
                String key = y + "/" + x;
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            // +1 to include original point
            res = Math.max(res, max + sameP + 1);
        }
        return res;
    }

    private int gcd(int x, int y) {
        if (y == 0) return x;
        return gcd(y, x % y);
    }
}

Additional