LeetCode 149 Max Points on Line - Example and Complexity Analysis

Trace points = [[0,0], [1,1], [2,2], [1,0]].

Anchor at [0,0]:

• Slope to [1,1]: dy=1, dx=1 → reduced (1,1)
• Slope to [2,2]: dy=2, dx=2 → reduced (1,1)
• Slope to [1,0]: dy=0, dx=1 → reduced (0,1)

Slope map: {(1,1): 2, (0,1): 1}. Max is $2$. With anchor, that's $3$ collinear points.

Anchor at [1,1]:

• Slope to [0,0]: (-1,-1) → reduced (1,1)
• Slope to [2,2]: (1,1) → reduced (1,1)
• Slope to [1,0]: (-1,0) → reduced (1,0)

Slope map: {(1,1): 2, (1,0): 1}. Same result: $3$ collinear.

You check $n$ anchors. For each, compute slopes to $n-1$ others. That's $O(n^2)$ total time.

Each anchor's slope map uses at most $O(n)$ space.