Maximum Points on a Line
AmazonThe problem
Given an array of unqiue points nums, where each point is represented as nums[i] = [xi, yi] on a 2D plane, find the maximum number of points that lie on the same line.
Input: nums = [[0,0], [1,1], [2,2], [3,3]] Output: 4 Explanation: All four points lie on the line with slope 1, so the maximum number of points on the same line is 4.
Input: nums = [[0,1], [2,3], [4,5], [1,2], [3,4], [2,2]] Output: 5 Explanation: The points [0,1], [1,2], [2,3], [3,4], and [4,5] all lie on the same straight line, so the maximum number is 5.
Input: nums = [[2,3], [3,4], [5,1], [7,2], [6,5], [9,4]]
- 1 <= nums.length <= 500
- nums[i].length == 2
- -104 <= xi, yi <= 104
cpp
class Solution {
public:
int maximumPointsOnALine(vector<vector<int>> & nums) {
}
};java
class Solution {
public int maximumPointsOnALine(int[][] nums) {
}
}python
class Solution:
def maximumPointsOnALine(self, nums):javascript
class Solution {
maximumPointsOnALine(nums) {
}
}csharp
public class Solution
{
public int MaximumPointsOnALine(int[][] nums)
{
}
}go
func maximumPointsOnALine(nums [][]int) intStuck? Show a way to structure it+
- 01Choose each point as an anchor
- 02Count normalized slopes to later points
- 03Reduce delta pairs by gcd
- 04Canonicalize signs and vertical or horizontal lines
- 05Add duplicates and track the largest bucket
Reference answer
Then expect these follow-ups
How do you normalize (-2,-4) and (1,2)?
Tests: follow-up reasoning
What changes if coordinates exceed 32-bit range?
Tests: constraint adaptation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question