Max Points on a Line
3 min readJan 10, 2023
From O(n³) to O(n²)
It’s been a while not coding on the LC platform. Today I just solved an interesting geometry problem and I’d like to share my solution here:
Problem
Ideas
Solve the problem brute force. Since n is relatively small, a O(n³) solution is doable. However, we do can improve the complexity to O(n²) and the main idea is:
- 1) Check all possible lines by looking pairwise points as two points define a line. Say those two points are point i and j.
- 2) Organize point i and j to the line defined by point i and j.
- 3) In order to do 2), we need find a way to define a line.
- 4) I am using k and b to define a line based on y = k*x + b. Since k = dy / dx, I futher use dy and dx to replace k. Also, b can be floating point number.
- 5) In order to solve the floating point comparison issue for b, I change it to an integer number by multiplying it by a large number.
O(n³) solution
class Solution {
public:
bool is_a_line(vector<vector<int>>& a, int i, int j, int k){
int x1 = a[i][0], x2 = a[j][0], x3 = a[k][0];
int y1 = a[i][1], y2 = a[j][1], y3 = a[k][1];
if (x1 == x2) return x2 == x3;
// check wehter the slopes are the same for two lines
// by (point 1, 2) and (point 2, 3).
// (y2-y1)/(x2-x1) == (y3-y2)/(x3-x2)
return (y2 - y1)*(x3 - x2) == (y3- y2)*(x2-x1);
}
int maxPoints(vector<vector<int>>& a) {
const int n = a.size();
if (n <= 2) return int(n);
int ret = 0, this_ret=0;
for (int i = 0; i < n-2; ++i)
{
for (int j = i + 1; j < n-1; ++j)
{
this_ret = 2;
for (int k = j +1; k < n; ++k)
{
this_ret += is_a_line(a, i, j, k);
}
ret = max(ret, this_ret);
}
}
return ret;
}
};O(n²) solution (adjusted from [1])
class Solution {
public:
vector<int> get_dy_dx_b(vector<vector<int>>& a, int i, int j){
/*
We know equation of: y = kx + b
where k = dy/dx and b is the value of y when x = 0.
Of course, we need process some special case such as dx = 0
*/
int x1 = a[i][0], x2 = a[j][0];
int y1 = a[i][1], y2 = a[j][1];
if (x1 == x2) return {1, 0, x1};
if (y1 == y2) return {0, 1, y1};
int dy = y2 - y1, dx = x2 - x1;
int _gcd = gcd(dy, dx);
dy /= _gcd;
dx /= _gcd;
// get b, as the floating point number has accuracy issue, let's mutiple b by 1000000 and get an integer.
//k = dy/dx
// k*x1 + b = y1 -> b = y1 - k*x1
double b = y1 - x1*double(dy)/double(dx);
int C = 10000;
return {dy, dx, int(C*b)};
}
int maxPoints(vector<vector<int>>& a) {
const int n = a.size();
if (n <= 2) return int(n);
map<vector<int>, unordered_set<int>> cnt;
for (int i = 0; i < n - 1; ++i)
for (int j = i + 1; j < n; ++j){
auto key = get_dy_dx_b(a, i, j);
cnt[key].insert(i);
cnt[key].insert(j);
}
int ret = 0;
for (auto [_, v]: cnt) ret = max(ret, (int)v.size());
return ret;
}
private:
int gcd(int a, int b){
return b == 0? a : gcd(b, a % b);
}
};