HardCoding

Maximum Points on a Line

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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)
    {
       
    }

}

func maximumPointsOnALine(nums [][]int) int

Solve on LeetCode →

Stuck? 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

Anchor every candidate line

For each point i, count how many other points have the same slope relative to it. Represent a slope by (dy/g, dx/g), where g = gcd(abs(dy), abs(dx)); normalize signs so equivalent fractions use exactly one key, for example force dx > 0, and use fixed keys for vertical and horizontal lines. Identical points are counted separately as duplicates and are added to every slope count for that anchor.

Why it works

All points on one line through the anchor share the same normalized direction, while different directions get different keys. The largest slope bucket plus the anchor and duplicate count is the best line through that anchor; taking the maximum over anchors finds the global answer. Be explicit about duplicate coordinates and negative deltas, since raw floating-point slopes split equal lines. With n points, time is O(n^2 log C) for gcd work, often described as O(n^2); extra space is O(n) per anchor.

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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question