149. Max Points on a Line

Difficulty:
Related Topics:
Similar Questions:

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

/**
 * Definition for a point.
 * function Point(x, y) {
 *     this.x = x;
 *     this.y = y;
 * }
 */
/**
 * @param {Point[]} points
 * @return {number}
 */
var maxPoints = function(points) {
  var max = 0;
  var map = {};
  var localMax = 0;
  var samePoint = 0;
  var k = 0;
  var len = points.length;
  for (var i = 0; i < len; i++) {
    map = {};
    localMax = 0;
    samePoint = 1;
    for (var j = i + 1; j < len; j++) {
      if (points[i].x === points[j].x && points[i].y === points[j].y) {
        samePoint++;
        continue;
      }
        if (points[i].y === points[j].y) k = Number.MAX_SAFE_INTEGER;
        else k = (points[i].x - points[j].x) / (points[i].y - points[j].y);
        if (!map[k]) map[k] = 0;
        map[k]++;
        localMax = Math.max(localMax, map[k]);
    }
    localMax += samePoint;
    max = Math.max(max, localMax);
  }
  return max;
};

Explain:

nope.

Complexity: