Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
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
Constraints:
1 <= points.length <= 300points[i].length == 2-104 <= xi, yi <= 104points are unique.#149 Max Points on a Line asks you to determine the largest number of points that lie on the same straight line in a 2D plane. A common strategy is to treat each point as an anchor and compute the slope it forms with every other point. If multiple points share the same slope relative to the anchor, they belong to the same line.
To efficiently track slopes, use a hash table where the key represents a normalized slope (for example using a reduced fraction dy/dx computed with GCD). This avoids floating‑point precision issues and ensures identical slopes are grouped together. While scanning other points, count how many share the same slope with the anchor. Also handle special cases such as duplicate points and vertical lines.
The process is repeated for every point as the base, and the maximum count across all anchors gives the answer. This geometric hashing approach balances accuracy and efficiency for the problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with slope normalization (anchor point technique) | O(n²) | O(n) |
NeetCodeIO
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
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is considered a classic geometry and hashing interview question. Variants of it appear in technical interviews at companies like Google, Amazon, and Meta because it tests mathematical reasoning, edge case handling, and hash map usage.
A hash table is typically used to store slope frequencies for each anchor point. The key represents a normalized slope pair such as (dy, dx), and the value tracks how many points share that slope relative to the base point.
Slope values like 2/4 and 1/2 represent the same line but would appear different if stored directly. Using the greatest common divisor (GCD) reduces the fraction to its canonical form, ensuring identical slopes map to the same key in the hash table.
The optimal approach treats each point as a base point and calculates slopes to every other point. A hash map groups points with the same slope, allowing you to count how many lie on the same line. Normalizing slopes using GCD helps avoid floating point errors.
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.