149. Max Points on a Line

At a Glance

Topic: math-geometry
Pattern: Co-linearity via reduced slope (hash map) — plain text + prefix patterns not central
Difficulty: Hard
Companies: Google, Amazon, Affirm, DoorDash, Indeed
Frequency: Medium
LeetCode: 149

Problem (one-liner)

Given an array of [x, y] integer coordinates, return the maximum number of points that lie on one straight line.

Recognition Cues

Geometry + counting points sharing same slope from a fixed anchor
Duplicates are same point — fold into a separate counter
Use exact rational slope — reduce (deltaY, deltaX) by gcd to avoid float error

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Float slope — precision traps with large coordinates.
Pair reduced by gcd + map — O(n^2) time, O(n) space per anchor — optimal for general arrays (problem constraints).

Optimal Solution

Go

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func absValue(value int) int {
	if value < 0 {
		return -value
	}
	return value
}

func maxPoints(points [][]int) int {
	pointCount := len(points)
	if pointCount <= 2 {
		return pointCount
	}
	answer := 0
	for anchorIndex := 0; anchorIndex < pointCount; anchorIndex++ {
		slopeCounts := map[[2]int]int{}
		duplicates := 0
		for otherIndex := 0; otherIndex < pointCount; otherIndex++ {
			if otherIndex == anchorIndex {
				continue
			}
			deltaY := points[otherIndex][1] - points[anchorIndex][1]
			deltaX := points[otherIndex][0] - points[anchorIndex][0]
			if deltaY == 0 && deltaX == 0 {
				duplicates++
				continue
			}
			// Vertical vs horizontal need distinct keys after normalization
			if deltaX == 0 {
				deltaY = 1
				deltaX = 0
			} else if deltaY == 0 {
				deltaY = 0
				deltaX = 1
			} else {
				greatest := gcd(absValue(deltaY), absValue(deltaX))
				deltaY /= greatest
				deltaX /= greatest
				if deltaX < 0 {
					deltaY = -deltaY
					deltaX = -deltaX
				}
			}
			key := [2]int{deltaY, deltaX}
			slopeCounts[key]++
		}
		localBest := duplicates
		for _, count := range slopeCounts {
			if count+duplicates > localBest {
				localBest = count + duplicates
			}
		}
		if localBest+1 > answer {
			answer = localBest + 1
		}
	}
	return answer
}

JavaScript

function gcd(left, right) {
  while (right !== 0) {
    const temp = right;
    right = left % right;
    left = temp;
  }
  return left;
}

function maxPoints(points) {
  const pointCount = points.length;
  if (pointCount <= 2) {
    return pointCount;
  }
  let answer = 0;
  for (let anchorIndex = 0; anchorIndex < pointCount; anchorIndex += 1) {
    const slopeCounts = new Map();
    let duplicates = 0;
    for (let otherIndex = 0; otherIndex < pointCount; otherIndex += 1) {
      if (otherIndex === anchorIndex) {
        continue;
      }
      let deltaY = points[otherIndex][1] - points[anchorIndex][1];
      let deltaX = points[otherIndex][0] - points[anchorIndex][0];
      if (deltaY === 0 && deltaX === 0) {
        duplicates += 1;
        continue;
      }
      if (deltaX === 0) {
        deltaY = 1;
        deltaX = 0;
      } else if (deltaY === 0) {
        deltaY = 0;
        deltaX = 1;
      } else {
        const greatest = gcd(Math.abs(deltaY), Math.abs(deltaX));
        deltaY /= greatest;
        deltaX /= greatest;
        if (deltaX < 0) {
          deltaY = -deltaY;
          deltaX = -deltaX;
        }
      }
      const key = `${deltaY},${deltaX}`;
      slopeCounts.set(key, (slopeCounts.get(key) || 0) + 1);
    }
    let localBest = duplicates;
    for (const count of slopeCounts.values()) {
      if (count + duplicates > localBest) {
        localBest = count + duplicates;
      }
    }
    answer = Math.max(answer, localBest + 1);
  }
  return answer;
}

Walkthrough

Anchor at (1,1); vectors to collinear points share reduced slope (dy,dx). Duplicate coordinates increment duplicates without affecting slope key.

Invariant: For fixed anchor, each bucket counts points along one ray/line through anchor.

Edge Cases

All identical points — n
Vertical lines — encoded as (1, 0) after normalization
Integer overflow on delta — use int64 in production if language requires

Pitfalls

Floating slopes — reject for interviews at this difficulty
Forgetting +1 for anchor itself when reporting line size

Variants

3D collinear points — two independent direction vectors
Max points on circle — different geometry
Online stream of points — approximate / windowed structures

Mind-Map Tags

#slope-hash #gcd-normalize #duplicates #pair-key #o-n-squared