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.
1import java.util.*;
2
3class Solution {
4 public int maxPoints(int[][] points) {
5 if (points.length <= 1) return points.length;
6 int maxPoints = 1;
7
8 for (int i = 0; i < points.length; i++) {
9 Map<Double, Integer> slopeMap = new HashMap<>();
10 for (int j = 0; j < points.length; j++) {
11 if (i != j) {
12 int dx = points[j][0] - points[i][0];
13 int dy = points[j][1] - points[i][1];
14 double slope = dx == 0 ? Double.POSITIVE_INFINITY : (double) dy / dx;
15 slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
16 maxPoints = Math.max(maxPoints, slopeMap.get(slope) + 1);
17 }
18 }
19 }
20 return maxPoints;
21 }
22}This solution in Java mirrors the logic of calculating slopes and counting them in a HashMap, then finding the max count.
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.
1#include <vector>
2#include <unordered_map>
3#include <cmath>
4#include <tuple>
5using namespace std;
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if (n <= 1) return n;
int max_points = 1;
for (int i = 0; i < n; ++i) {
unordered_map<string, int> line_count;
for (int j = 0; j < n; ++j) {
if (i != j) {
int a = points[i][1] - points[j][1];
int b = points[j][0] - points[i][0];
int c = points[i][0] * points[j][1] - points[j][0] * points[i][1];
int g = gcd(gcd(abs(a), abs(b)), abs(c));
a /= g;
b /= g;
c /= g;
string line = to_string(a) + '/' + to_string(b) + '/' + to_string(c);
line_count[line]++;
max_points = max(max_points, line_count[line] + 1);
}
}
}
return max_points;
}
};
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}The C++ solution builds on the ax + by + c line representation using gcd normalization, employing string keys for the cache to manage line counts efficiently.