Max Points on a Line - Video Solutions

Problem Overview: You are given an array of 2D points. The task is to determine the maximum number of points that lie on the same straight line. Any two points define a line, but multiple points can share the same slope relative to an anchor point, indicating collinearity.

Approach 1: Using Slope Calculation with Hashmap (Time: O(n^2), Space: O(n))

Fix one point as an anchor and compute the slope between that point and every other point. If multiple points share the same slope relative to the anchor, they lie on the same line. Store slope frequencies in a hash map where the key represents the slope (typically normalized as a reduced fraction using GCD to avoid floating‑point precision issues). Each iteration resets the map for a new anchor point. Track duplicates separately because identical coordinates create multiple overlapping points on the same line. This approach relies heavily on fast hash lookups and careful slope normalization. It works well because any line through the anchor is uniquely identified by its slope. Problems involving coordinate pairs often combine array traversal with slope hashing techniques from math and hash table design.

Approach 2: Using Line Equation with Hashmap (Time: O(n^2), Space: O(n^2))

Instead of anchoring one point and counting slopes, compute the full line equation formed by every pair of points. A line in 2D can be expressed as Ax + By + C = 0. Normalize the coefficients using the greatest common divisor so equivalent lines map to the same representation. Store each line equation as a key in a hash map and track the set or count of points that lie on it. Because every pair generates a line entry, the map may grow larger than the slope-based method. This method is more explicit from a geometry standpoint and avoids vertical line edge cases, but requires careful normalization to ensure identical lines produce identical keys. It highlights core ideas from computational geometry.

Recommended for interviews: The slope-with-hashmap approach is what most interviewers expect. It demonstrates understanding of geometric properties, hashing, and edge cases such as vertical lines, horizontal lines, and duplicate points. The line equation method shows deeper geometry knowledge but is less common due to higher space overhead. Starting with the slope-based solution and discussing normalization and duplicates usually signals strong problem‑solving ability.