Max Points on a Line - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
Complexity
Time Complexity: O(n^2), from comparing each pair of points.
Space Complexity: O(n), for storing normalized line equations.
Approach 3: Default Approach
Try this approach in the editor →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 | — |
Detailed 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 |
Video Solution
Leetcode 149 - Maximum Points on a Line - Python • NeetCodeIO • 34,128 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Max Points on a Line easy or hard?
Max Points on a Line Python/Java solution
How to solve Max Points on a Line in O(n)?
What is the best approach for Max Points on a Line?
Is Max Points on a Line asked at Google/Amazon/Meta?
What data structure is used in Max Points on a Line?
What is the time complexity of Max Points on a Line?
Ready to solve this problem?
Practice Max Points on a Line with our built-in code editor and test cases.
Practice on FleetCode