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.
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.