Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Example 1:
Input: points = [[1,1],[2,2],[3,3]] Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4
Constraints:
1 <= points.length <= 300points[i].length == 2-104 <= xi, yi <= 104- All the
pointsare unique.
Companies: Oracle, Cisco, Amazon, Apple, Sprinklr, tcs, LinkedIn, Google, Microsoft, MakeMyTrip, Adobe, Uber, Bloomberg, Twitter
Related Topics:
Array, Hash Table, Math, Geometry
Similar Questions:
- Line Reflection (Medium)
- Minimum Number of Lines to Cover Points (Medium)
- Minimum Lines to Represent a Line Chart (Medium)
Firstly, assume there are no duplicate points.
We keep a list of lines, each of which is a list of points on that line. We push the first line which is formed by the first two points a and b into it. So now the lines becomes:
(a, b)
Then we visit the other points one by one. For the third point c, we traverse through the lines and see if c is in any of the lines.
Assume c is not on line (a, b), we add (a, c) and (b, c) to the lines.
(a, b)
(a, c)
(b, c)
For the next point d, assume d is on line (b, c) but not on the other lines, then add d into this line.
(a, b)
(a, c)
(b, c, d)
And at the same time we know b and c are d's neighbor (i.e. they are on the same line), and a is not d's neighbor. So we add line (a, d) to the lines.
(a, b)
(a, c)
(b, c, d)
(a, d)
We keep visiting the points in this way. The final result will be the length of longest line.
Now, what if our assumption "there are no duplicate points" is wrong? Just merge the same points into one entry, and take a note of its count. The other logics are the same.
// OJ: https://leetcode.com/problems/max-points-on-a-line/
// Author: github.com/lzl124631x
// Time: O(N^3)
// In worse case, when visiting ith point, there will be O(i^2)
// lines, but all the lines are of constant size 2. So in
// sum it's O(N^3), not O(N^4).
// Space: O(N^2)
namespace std {
template <> struct hash<Point> {
std::size_t operator () (const Point &p) const {
return hash<int>()(p.x) ^ hash<int>()(p.y);
}
};
}
bool operator==(const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}
class Solution {
private:
bool onSameLine(Point &a, Point &b, Point &c) {
return (long long)(a.x - b.x) * (a.y - c.y) == (long long)(a.x - c.x) * (a.y - b.y);
}
public:
int maxPoints(vector<Point>& points) {
if (points.size() <= 2) return points.size();
unordered_map<Point, int> m;
for (auto p : points) m[p]++;
vector<pair<Point, int>> ps(m.begin(), m.end());
vector<vector<int>> lines(1, vector<int>{ 0, 1 });
int N = ps.size();
for (int i = 2; i < N; ++i) {
auto &p = ps[i].first;
vector<int> bad(i, 1);
for (auto &line : lines) {
auto &p1 = ps[line[0]].first, &p2 = ps[line[1]].first;
if (!onSameLine(p1, p2, p)) continue;
for (int neighbor : line) bad[neighbor] = 0;
line.push_back(i);
}
for (int j = 0; j < i; ++j) {
if (bad[j]) lines.emplace_back(vector<int>{ j, i });
}
}
int ans = 2;
for (auto line : lines) {
int cnt = 0;
for (auto i : line) cnt += ps[i].second;
ans = max(ans, cnt);
}
return ans;
}
};// OJ: https://leetcode.com/problems/max-points-on-a-line
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int maxPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
for (int i = 0; i < N; ++i) { // Use A[i] as point1
unordered_map<double, int> m;
int mx = 0;
for (int j = i + 1; j < N; ++j) { // Use A[j] as point2
int x1 = A[i][0], y1 = A[i][1];
int x2 = A[j][0], y2 = A[j][1];
if ((x1 > x2) || (x1 == x2 && y1 < y2)) swap(x1, x2), swap(y1, y2); // make sure these two points are ordered
mx = max(mx, ++m[atan2(x2 - x1, y2 - y1)]); // cout the frequency of angles
}
ans = max(ans, mx + 1);
}
return ans;
}
};