Max Points on a Line
The key idea
Two points always share a line, so fix one point as an anchor and group every other point by the slope of the line from the anchor to it. All points with the same slope from the anchor are collinear with it. The largest slope group plus the anchor itself is the best line through that anchor.
Problem
You are given an array points where points[i] = [xi, yi] is a point on the X-Y plane. Return the maximum number of points that lie on the same straight line.
Every point counts toward a line it lies on, and two points are always enough to define a line, so the answer is at least 1 (or 2 when there are two or more points). The challenge is finding the single line that passes through the most points at once.
Constraints
1 <= points.length <= 300points[i].length == 2-10^4 <= xi, yi <= 10^4- All the
pointsare unique.
Examples
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Complexity
Time: O(n^2) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY