Quick Overview

Find the most points on one line using exact coordinate relationships, including repeated points and vertical or horizontal lines.

Count the Maximum Number of Collinear Points

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given points in a two-dimensional plane, return the largest number of input points that lie on one straight line. ### Function Contract Implement `maximum_collinear_points(points) -> int`, where every element of `points` is an integer pair `[x, y]`. ### Constraints and Clarifications The following bounds and repeated-point convention are explicit practice assumptions: - `0 <= len(points) <= 300`. - Coordinates are integers between `-1000000` and `1000000`, inclusive. - Repeated coordinates represent distinct input points and each counts toward the result. - Horizontal and vertical lines are allowed. - Return `0` for no points and `1` for a single point. - Collinearity is exact; do not use a floating-point tolerance that can merge different slopes. - Aim for `O(n^2)` pair processing, apart from integer-normalization costs. ### Examples ```text points = [[0, 0], [1, 1], [2, 2], [2, 0]] Output: 3 ``` Three points lie on the line `y = x`. ```text points = [[1, 1], [1, 1], [2, 2], [3, 4]] Output: 3 ``` The two occurrences of `(1, 1)` and the point `(2, 2)` lie on one line. ```hint Compare directions from one point Lines through a fixed point can be grouped by direction. Decide how to represent equal directions exactly and how coincident points should affect every possible line through that point. ```

Overview: Find the most points on one line using exact coordinate relationships, including repeated points and vertical or horizontal lines.

Read the full LinkedIn Software Engineer interview experience this question came from

You are given a list of points in a two-dimensional plane. Each point is an integer pair [x, y]. Return the largest number of input points that lie on one straight line. Implement maximum_collinear_points(points) -> int. Rules: - Repeated coordinates are distinct input points, and each one counts toward the result. A repeated point lies on every line through its location. - Horizontal and vertical lines are allowed. - Return 0 when there are no points and 1 when there is a single point. - Collinearity is exact. Do not use a floating-point tolerance that could merge two different slopes. Constraints: - 0 <= len(points) <= 300 - Each coordinate is an integer between -1000000 and 1000000, inclusive. - Coordinate differences stay within +/-2000000. The returned count fits in a 32-bit int, but the intermediate arithmetic used to decide collinearity does not: an exact cross product of two coordinate differences reaches about 4e12, and a combined key built from a reduced direction pair can reach about 1e13. Use 64-bit integers for such intermediate values (long in Java, long long in C++). Every value involved stays well below 2^53, so JavaScript numbers remain exact. Example 1: Input: points = [[0, 0], [1, 1], [2, 2], [2, 0]] Output: 3 Explanation: (0, 0), (1, 1) and (2, 2) lie on the line y = x. Example 2: Input: points = [[1, 1], [1, 1], [2, 2], [3, 4]] Output: 3 Explanation: Both occurrences of (1, 1) and the point (2, 2) lie on one line.

Constraints

  • 0 <= len(points) <= 300
  • Each point is an integer pair [x, y] with -1000000 <= x, y <= 1000000
  • Repeated coordinates are distinct input points and each counts toward the result
  • Horizontal and vertical lines are allowed
  • Return 0 for no points and 1 for a single point
  • Collinearity is exact; do not use a floating-point tolerance

Examples

Input: ([],)

Expected Output: 0

Explanation: No points returns 0.

Input: ([[5, -7]],)

Expected Output: 1

Explanation: A single point returns 1.

Hints

  1. Every line that contains at least two input points is determined by any two of them. Try fixing one point and grouping the others by how they relate to it.
  2. Two directions from the same point describe the same line only when they are exactly proportional. Choose a representation in which proportional directions compare equal without using floating-point division.
  3. A point with the same coordinates as the fixed point lies on every line through it, so count such points separately from the direction groups.

Loading coding console...

Show the approach

Approach

Algorithm: with 0, 1 or 2 points the answer is the number of points, since any two points share a line. Otherwise, fix each index i as an anchor and look only at later indices j > i. A point j with the same coordinates as the anchor increments a 'same' counter. Any other point gives a direction (dx, dy), which is reduced by gcd(|dx|, |dy|) and sign-normalized so that dx > 0, or dx == 0 and dy > 0. Two points then lie on the same line through the anchor exactly when their reduced directions are equal. For this anchor the best line has same + (largest direction bucket) points, where 'same' already includes the anchor. The answer is the maximum over all anchors.

Invariant and correctness: take an optimal line L and let i be the smallest index of any point on L. Every other point on L has a larger index and is either a copy of point i (counted in 'same') or lies in one reduced direction bucket. Integer gcd reduction with sign normalization maps (a, b) and (ka, kb) to the same key for every nonzero integer k, including negative k, and never maps directions of different slopes together. So anchor i counts exactly |L|. No anchor counts more than one line's points, so the maximum is exact. No floating-point value is used, so nearly equal slopes near the +/-1000000 bounds stay separate.

Edge cases: empty input returns 0 and one point returns 1. When every point is identical, the direction map stays empty and 'same' equals n. Duplicates count on every line through their location, because copies with later indices are added to whichever bucket wins for that anchor. Vertical lines normalize to (0, 1) and horizontal lines to (1, 0). Each coordinate difference stays within +/-2000000, which fits in 32 bits, but the combined Java/C++ bucket key reaches about 1e13 and must be held in a 64-bit integer; it stays below 2^53, so the JavaScript reference is exact as well.

Time complexity:
O(n^2 log C), where C = 2000000 bounds the gcd arguments
Space complexity:
O(n)