Max Points on a Line solution and explanation
Cisco
Google
9 more videos on this problem
Leetcode 149 - Maximum Points on a Line - PythonNeetCodeIO · 8:14 · 34K views
149. Max Points on a Line | LEETCODE HARD | GEOMETRY | CODE EXPLAINERcode Explainer · 7:00 · 18K views
LeetCode 149. Max Points on a Line Explanation and Solutionhappygirlzt · 10:04 · 11K views
Max Points on a Line -(Google, Apple, LinkedIn, Amazon) : Explanation ➕ Live CodingcodestorywithMIK · 36:43 · 11K views
Max points on a line problem (LeetCode #149) - Inside codeInside code · 8:49 · 7K views
LeetCode 149. Max Points on a LineHappy Coding · 16:42 · 4K views
Daily Leetcode #1013: Jan 08, 2023 - 149. Max Points on a LineProgramming Live with Larry · 13:12 · 953 views
LeetCode | 149 Max Points on a Line | Python3 | Explanationygongcode · 20:18 · 950 views
Max Points on a Line | Leetcode #149 \ Code ExplorerCode Explorer · 6:40 · 949 views
Max Points on a Line | LeetCode 149 | JavaThe TryIt Project · 16:15 · 599 views
The problem
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 <= 104- All the
pointsare unique.
Approach overview
Problem Overview: You are given an array of 2D points. The task is to determine the maximum number of points that lie on the same straight line. Any two points define a line, but multiple points can share the same slope relative to an anchor point, indicating collinearity.
Approach 1: Using Slope Calculation with Hashmap (Time: O(n^2), Space: O(n))
Fix one point as an anchor and compute the slope between that point and every other point. If multiple points share the same slope relative to the anchor, they lie on the same line. Store slope frequencies in a hash map where the key represents the slope (typically normalized as a reduced fraction using GCD to avoid floating‑point precision issues). Each iteration resets the map for a new anchor point. Track duplicates separately because identical coordinates create multiple overlapping points on the same line. This approach relies heavily on fast hash lookups and careful slope normalization. It works well because any line through the anchor is uniquely identified by its slope. Problems involving coordinate pairs often combine array traversal with slope hashing techniques from math and hash table design.
Approach 2: Using Line Equation with Hashmap (Time: O(n^2), Space: O(n^2))
Instead of anchoring one point and counting slopes, compute the full line equation formed by every pair of points. A line in 2D can be expressed as Ax + By + C = 0. Normalize the coefficients using the greatest common divisor so equivalent lines map to the same representation. Store each line equation as a key in a hash map and track the set or count of points that lie on it. Because every pair generates a line entry, the map may grow larger than the slope-based method. This method is more explicit from a geometry standpoint and avoids vertical line edge cases, but requires careful normalization to ensure identical lines produce identical keys. It highlights core ideas from computational geometry.
Recommended for interviews: The slope-with-hashmap approach is what most interviewers expect. It demonstrates understanding of geometric properties, hashing, and edge cases such as vertical lines, horizontal lines, and duplicate points. The line equation method shows deeper geometry knowledge but is less common due to higher space overhead. Starting with the slope-based solution and discussing normalization and duplicates usually signals strong problem‑solving ability.
Approach 1: Approach 1: Using Slope Calculation with Hashmap
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.
from collections import defaultdict
from math import gcd
class Solution:
def maxPoints(self, points: list[list[int]]) -> int:
def calculate_slope(p1, p2):
dx = p2[0] - p1[0]
dy = p2[1] - p1[1]
if dx == 0:
return (float('inf'), 0)
if dy == 0:
return (0, float('inf'))
g = gcd(dx, dy)
return (dy // g, dx // g)
max_points = 1
n = len(points)
for i in range(n):
slope_count = defaultdict(int)
for j in range(n):
if i != j:
slope = calculate_slope(points[i], points[j])
slope_count[slope] += 1
max_points = max(max_points, slope_count[slope] + 1)
return max_pointsimport java.util.*;
class Solution {
public int maxPoints(int[][] points) {
if (points.length <= 1) return points.length;
int maxPoints = 1;
for (int i = 0; i < points.length; i++) {
Map<Double, Integer> slopeMap = new HashMap<>();
for (int j = 0; j < points.length; j++) {
if (i != j) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
double slope = dx == 0 ? Double.POSITIVE_INFINITY : (double) dy / dx;
slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
maxPoints = Math.max(maxPoints, slopeMap.get(slope) + 1);
}
}
}
return maxPoints;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
using 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<double, int> slope_count;
for (int j = 0; j < n; ++j) {
if (i != j) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
double slope = dx == 0 ? INT_MAX : static_cast<double>(dy) / dx;
slope_count[slope]++;
max_points = max(max_points, slope_count[slope] + 1);
}
}
}
return max_points;
}
};The solution iterates over each point and calculates the slope with every other point, using a hashmap to track and count each slope. The greatest count of any slope originating from a point plus one (for the point itself) gives the maximum number of points on a line through that point.
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.
Approach 2: Approach 2: Using Line Equation with Hashmap
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.
from collections import defaultdict
from math import gcd
class Solution:
def maxPoints(self, points: list[list[int]]) -> int:
def line_equation(p1, p2):
a = p1[1] - p2[1]
b = p2[0] - p1[0]
c = p1[0] * p2[1] - p2[0] * p1[1]
g = gcd(gcd(abs(a), abs(b)), abs(c))
return (a // g, b // g, c // g)
max_points = 1
n = len(points)
for i in range(n):
lines = defaultdict(int)
for j in range(n):
if i != j:
line = line_equation(points[i], points[j])
lines[line] += 1
max_points = max(max_points, lines[line] + 1)
return max_points#include <vector>
#include <unordered_map>
#include <cmath>
#include <tuple>
using 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);
}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.
Time Complexity: O(n^2), from comparing each pair of points.
Space Complexity: O(n), for storing normalized line equations.
Approach 3: Default Approach
public class Solution {
public int MaxPoints(int[][] points) {
int n = points.Length;
int ans = 1;
for (int i = 0; i < n; ++i) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = i + 1; j < n; ++j) {
int x2 = points[j][0], y2 = points[j][1];
int cnt = 2;
for (int k = j + 1; k < n; ++k) {
int x3 = points[k][0], y3 = points[k][1];
int a = (y2 - y1) * (x3 - x1);
int b = (y3 - y1) * (x2 - x1);
if (a == b) {
++cnt;
}
}
if (ans < cnt) {
ans = cnt;
}
}
}
return ans;
}
}func maxPoints(points [][]int) int {
n := len(points)
ans := 1
for i := 0; i < n; i++ {
x1, y1 := points[i][0], points[i][1]
for j := i + 1; j < n; j++ {
x2, y2 := points[j][0], points[j][1]
cnt := 2
for k := j + 1; k < n; k++ {
x3, y3 := points[k][0], points[k][1]
a := (y2 - y1) * (x3 - x1)
b := (y3 - y1) * (x2 - x1)
if a == b {
cnt++
}
}
if ans < cnt {
ans = cnt
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Slope Calculation with Hashmap | 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. |
| Approach 2: Using Line Equation with Hashmap | Time Complexity: O(n^2), from comparing each pair of points. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Slope Calculation with Hashmap | O(n^2) | O(n) | Standard interview solution; efficient counting of collinear points from an anchor point |
| Line Equation with Hashmap | O(n^2) | O(n^2) | When explicitly modeling geometric lines or avoiding slope edge cases like vertical lines |
Frequently asked questions
Is Max Points on a Line easy or hard?
Max Points on a Line is classified as a hard problem because it combines geometry, hashing, and careful edge case handling. Challenges include slope normalization, vertical lines, duplicate points, and avoiding floating‑point precision errors.
Max Points on a Line Python/Java solution
Typical Python and Java solutions iterate through points, compute normalized slopes using GCD to avoid floating point errors, and store counts in a hash map. The maximum slope frequency plus duplicate points determines the number of collinear points.
How to solve Max Points on a Line in O(n)?
Solving the problem in O(n) time is not possible in the general case because determining collinearity requires comparing pairs of points. The best known approach is O(n^2) using slope hashing or line normalization.
What is the best approach for Max Points on a Line?
The most practical approach fixes each point as an anchor and counts slopes to every other point using a hash map. Points with the same normalized slope relative to the anchor lie on the same line. This solution runs in O(n^2) time and O(n) space and is the most common interview implementation.
Is Max Points on a Line asked at Google/Amazon/Meta?
Max Points on a Line appears in interviews at companies that emphasize geometry and hashing techniques, including Google, Amazon, and Meta. It tests slope normalization, hash map usage, and careful handling of duplicates and vertical lines.
What data structure is used in Max Points on a Line?
A hash map is the primary data structure. It stores slope counts for each anchor point or normalized line equations when using the line representation method.
What is the time complexity of Max Points on a Line?
The optimal solution runs in O(n^2) time because each point is compared with every other point to compute slopes. For each anchor point, a hash map tracks slope frequencies in O(n) space.