Sponsored
Sponsored
In this approach, for each point, we will calculate the slope it forms with every other point and store the slope in a hashmap. The number of points with the same slope from a given point can determine the number of points on the same line. We need to be careful with slope representation by using a reduced form using GCD to handle precision issues.
Time Complexity: O(n^2), where n is the number of points. This is because we check each pair of points which leads to n * (n-1)/2 slope calculations.
Space Complexity: O(n), for storing the slopes in the hashmap.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int maxPoints(vector<vector<int>>& points) {
9 int n = points.size();
10 if (n <= 1) return n;
11 int max_points = 1;
12
13 for (int i = 0; i < n; ++i) {
14 unordered_map<double, int> slope_count;
15 for (int j = 0; j < n; ++j) {
16 if (i != j) {
17 int dx = points[j][0] - points[i][0];
18 int dy = points[j][1] - points[i][1];
19 double slope = dx == 0 ? INT_MAX : static_cast<double>(dy) / dx;
20 slope_count[slope]++;
21 max_points = max(max_points, slope_count[slope] + 1);
22 }
23 }
24 }
25 return max_points;
26 }
27};This C++ solution uses a similar approach by generating slopes for every point pair, storing these in an unordered map, and then finding the maximum count of slopes for each point.
Alternatively, instead of using slopes directly, we express a line using its coefficients in the line equation format ax + by + c = 0, using GCD to ensure uniqueness in line parameters. This approach confirms lines uniquely, facilitating easier comparisons.
Time Complexity: O(n^2), from comparing each pair of points.
Space Complexity: O(n), for storing normalized line equations.
1from collections import defaultdict
2from math import gcd
3
This implementation utilizes line equations represented in ax + by + c form, normalized using gcd, to track lines passing through each point. This avoids precision issues inherent with float slopes.