Max Points on a Line

1. Define the problem

Given points on a plane, each written as a pair [x, y], return the largest number of points that lie on one straight line . Pick one point as the anchor and look at every other point through it. Two points lie on the same line through the anchor when the direction from the anchor to each of them is the same. Describe that direction as a reduced step : take the horizontal and vertical gaps, divide both by their greatest common divisor, and flip the signs so the same line always produces the same pair of numbers. Use that pair as a hash map key and count how many points share it. The best answer for an anchor is its biggest tally plus one, because the anchor itself is on the line too.

Constraints

1 ≤ points.length ≤ 300
points_i.length == 2
-10⁴ ≤ x, y ≤ 10⁴
All points are different

Example

Inputpoints = [[1, 1], [2, 2], [3, 3], [4, 1]]

Output3

Explanation The points [1, 1], [2, 2] and [3, 3] all sit on the same diagonal line, so three is the most that share a line.

2. Know the words first

In plain terms

Greatest common divisor: The largest whole number that divides two numbers exactly. Dividing both gaps by it shrinks a step such as 4 across and 2 up down to 2 across and 1 up.
Reduced step: The smallest whole-number pair describing a direction, used here as the map key. Points 2 apart and 4 apart in the same direction share the key, so they are counted together.
Sign normalising: Forcing the key into one agreed form, here by making the horizontal part not negative. Without it, going left and going right along the same line would build two different keys.
Anchor point: The point all directions are measured from. Every point takes a turn, which is why a line is never missed.

3. Visualize the solution

One cell per direction key of the current anchor, plus the best answer so far

key 1—

key 2—

key 3—

best2

Statusinit

Four points, and the answer starts at 2 because any two points make a line.

What happens in this step

points = [[1,1], [2,2], [3,3], [4,1]]
There are more than 2 points, so the shortcut at the top does not fire.

best = 2
The first three cells will hold direction keys for one anchor at a time.

Step 1 of 6

Steps to visualize

The first three cells are the keys of the direction map for the anchor being worked on.
The label is the reduced step, such as 1/1 for one across and one up, and the value is how many points point that way.
The last cell holds the best count found so far, counting the anchor itself.
The map is emptied every time a new anchor is chosen.
A tally of d means d + 1 points on that line, because the anchor joins them.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per direction key of the current anchor, plus the best answer so far

key 1—

key 2—

key 3—

best2

Statusinit

Four points, and the answer starts at 2 because any two points make a line.

What happens in this step

points = [[1,1], [2,2], [3,3], [4,1]]
There are more than 2 points, so the shortcut at the top does not fire.

best = 2
The first three cells will hold direction keys for one anchor at a time.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function maxPoints(points) {
  if (points.length <= 2) {
    return points.length;
  }

  let best = 2;

  for (let i = 0; i < points.length; i++) {
    const slopes = new Map();

    for (let j = 0; j < points.length; j++) {
      if (i === j) {
        continue;
      }

      const dx = points[j][0] - points[i][0];
      const dy = points[j][1] - points[i][1];
      const divisor = gcd(Math.abs(dx), Math.abs(dy));
      let stepX = dx / divisor;
      let stepY = dy / divisor;

      if (stepX < 0 || (stepX === 0 && stepY < 0)) {
        stepX = -stepX;
        stepY = -stepY;
      }

      const key = stepX + '/' + stepY;
      const count = (slopes.get(key) || 0) + 1;

      slopes.set(key, count);

      if (count + 1 > best) {
        best = count + 1;
      }
    }
  }

  return best;
}

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

Time: O(n^2)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`points = [[1, 1], [2, 2], [3, 3], [4, 1]]`	`3`	example from the description
`points = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]`	`4`	a scattered set where the best line holds four points
`points = [[0, 0]]`	`1`	the early exit for one point
`points = [[0, 0], [1, 1]]`	`2`	two points always lie on a line
`points = [[0, 0], [0, 1], [0, 2], [1, 5]]`	`3`	a straight up and down line, where the horizontal gap is zero
`points = [[-1, -1], [0, 0], [1, 1], [5, 2]]`	`3`	negative coordinates, which is where sign normalising matters

Max Points on a Line