149. Max Points on a Line
1. Description
Given an array of points where points[i] = [$x_i$, $y_i$] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
2. Example
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
3. Constraints
- 1 <= points.length <= 300
- points[i].length == 2
- -$10^4$ <= xi, yi <= $10^4$
- All the points are unique.
4. Solutions
Math
n = points.size()
Time complexity: O($n^2$)
Space complexity: O(logn)
class Solution {
public:
int maxPoints(const vector<vector<int>> &points) {
const int n = points.size();
if (n <= 2) {
return n;
}
int max_points = 0;
for (int i = 0; i < n; ++i) {
unordered_map<pair<int, int>, int, pair_hash> line_points;
for (int j = i + 1; j < n; ++j) {
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
auto key = norm_slope(dx, dy);
++line_points[key];
max_points = max(line_points[key] + 1, max_points);
}
if (max_points > n / 2 || max_points >= n - i) {
break;
}
}
return max_points;
}
private:
static pair<int, int> norm_slope(int dx, int dy) {
if (dx == 0) {
return {1, 0};
}
if (dy == 0) {
return {0, 1};
}
int g = gcd(dx, dy);
dx /= g;
dy /= g;
if (dy < 0) {
dx = -dx;
dy = -dy;
}
return {dx, dy};
}
struct pair_hash {
size_t operator()(const pair<int, int> &slope) const noexcept {
return (uint64_t)(uint32_t)slope.first << 32 ^ (uint32_t)slope.second;
}
};
};