149. 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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Output: 3

Explanation:

Example 2

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

Output: 4

Explanation:

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n <= 1) return n;
        
        Map<String, Integer> slopeMap = new HashMap();
        int max = 0;
        
        for(int i = 0; i < n; i++) {
            int duplicate = 0;
            int tmpMax = 0;
            
            for(int j = i+1; j < n ; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if(dx == 0 && dy == 0) {
                    duplicate++;
                } else {
                    String slope = getSlopeKey(dx, dy);
                    slopeMap.put(slope, slopeMap.getOrDefault(slope, 0)+1);
                    tmpMax = Math.max(tmpMax, slopeMap.get(slope));
                }
            }
            max = Math.max(max, tmpMax+duplicate+1);
            slopeMap.clear();
        }
        
        return max;
    }
    
    private String getSlopeKey(int dx, int dy) {
        if(dx == 0) return "0-1";
        if(dy == 0) return "1-0";
        int d = gcd(dx, dy);
        return (dx/d) + "-" + (dy/d);
    }
    
    private int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a%b);
    }
}

Follow up