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:
- Time complexity : O(n^2).
- Space complexity : O(n).