149. Max Points on a Line

Problem

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

Solution (Java)

class Solution {
    public int maxPoints(int[][] points) {
        if (points.length < 2) {
            return points.length;
        }
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                int c = x * points[j][1] - y * points[j][0];
                int count = 2;
                for (int k = j + 1; k < points.length; k++) {
                    if (c == x * points[k][1] - y * points[k][0]) {
                        count++;
                    }
                }
                max = Math.max(count, max);
            }
        }
        return max;
    }
}

Solution (Javascript)

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function(points) {
    let N = points.length;
    if (N < 2){
        return N;
    }       

    let maxPoint = 0;
    let curMax, overlapPoints, verticalPoints;

    // Creating a map for storing the data.
    let slopeMap = new Map();

    // looping for each point
    for (let i = 0; i < N; i++)
    {
        curMax = 0;
        overlapPoints = 0;
        verticalPoints = 0;

        // looping from i + 1 to ignore same pair again
        for (let j = i + 1; j < N; j++)
        {
            // If both point are equal then just
            // increase overlapPoint count
            if (points[i] === points[j]){
                overlapPoints++;
            }

            // If x co-ordinate is same, then both
            // point are vertical to each other
            else if (points[i][0] === points[j][0]){
                verticalPoints++;
            }
            else{
                let yDif = points[j][1] - points[i][1];
                let xDif = points[j][0] - points[i][0];
                let g = gcd(xDif, yDif);

                // reducing the difference by their gcd
                yDif = Math.floor(yDif/g);
                xDif = Math.floor(xDif/g);

                // increasing the frequency of current slope.
                let tmp = [yDif, xDif];
                if(slopeMap.has(tmp.join(''))){
                    slopeMap.set(tmp.join(''), slopeMap.get(tmp.join('')) + 1);
                }
                else{
                    slopeMap.set(tmp.join(''), 1);
                }

                curMax = Math.max(curMax, slopeMap.get(tmp.join('')));
            }

            curMax = Math.max(curMax, verticalPoints);
        }

        // updating global maximum by current point's maximum
        maxPoint = Math.max(maxPoint, curMax + overlapPoints + 1);

        // printf("maximum collinear point
        // which contains current point
        // are : %d\n", curMax + overlapPoints + 1);
        slopeMap.clear();
    }

    return maxPoint;
};

// Function to find gcd of two numbers
let gcd = function(a, b) {
  if (!b) {
    return a;
  }
  return gcd(b, a % b);
}

Explain:

nope.

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(n).