Video Reading Section: Solving the “Max Points on a Line” Problem

Hello everyone, and welcome to our technical deep dive. Today, we’re tackling a classic and challenging problem from Meta’s interview question bank: “149. Max Points on a Line.”

This problem is a fantastic test of one’s ability to translate geometric intuition into efficient code, making heavy use of hash maps to optimize the solution.

Understanding the Problem

The problem statement is straightforward:

Given an array of points on the X-Y plane, we need to find the maximum number of points that lie on the same straight line.

Example:

• Input: [[1,1],[2,2],[3,3]]

• Output: 3 → all three points form a single line.

Challenge: Efficiently checking all possible lines formed by these points.

The Brute-Force Approach: A Starting Point

The most intuitive way is to check every possible triplet of points:

1. For every pair of points (i, j), define a line.

2. For every other point k, check if it lies on that line.

How to check? Use the slope concept: the slope between i and j should equal the slope between i and k for all three points to be colinear.

Problem with this approach:

• For 300 points, three nested loops → roughly O(n³) operations (~27 million comparisons).

• Too slow for platform constraints → we need a better solution.

The Optimized Hash Map Solution

We can improve efficiency from O(n³) to O(n²) using a hash map to store slopes.

Core Insight:

If a set of points lies on the same line, they all share the same slope relative to a common fixed point.

Step-by-Step Algorithm

1. Choose an Anchor Point: Iterate through each point i in the array and treat it as the anchor point.

2. Calculate Slopes: For every other point j (j > i), calculate the slope of the line formed by i and j.

3. Handle Special Cases:

   • Vertical line: x1 == x2 → slope is undefined → use a special value like INT_MAX.

   • Horizontal line: y1 == y2 → slope = 0.

   • General case: slope = (y2 - y1) / (x2 - x1).

4. Count with Hash Map:

   • Key → slope

   • Value → number of points (besides anchor) sharing this slope

   • Example: anchor i has 3 points with slope 0.5 → 4 points lie on the same line (anchor + 3 points).

5. Track Maximum: After checking all points for anchor i, the maximum count in the hash map + 1 (anchor) gives the max points on a line through i. Update the global maximum.

6. Repeat for All Anchors: Clear the hash map for each new anchor and repeat.

Why O(n²)?

• Outer loop → n times

• Inner loop → n-i times

• On average → O(n²) → efficient enough for n = 300.

C++ Implementation

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        // If there are 2 or fewer points, they always form a line.
        if (n <= 2) return n;

        int maxPoints = 2; // Minimum answer for n > 2 is 2.

        // Iterate through each point as the anchor.
        for (int i = 0; i < n; i++) {
            unordered_map<double, int> slopeCount; // Store count of points per slope.

            // For current anchor i, check all points j after it.
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];

                double slope;
                // Vertical line (undefined slope)
                if (x1 == x2) {
                    slope = INT_MAX;
                }
                // Horizontal line (zero slope)
                else if (y1 == y2) {
                    slope = 0.0;
                }
                // General case
                else {
                    slope = (double)(y2 - y1) / (double)(x2 - x1);
                }

                // Increment count for this slope
                slopeCount[slope]++;
                // Update global maximum (+1 for anchor)
                maxPoints = max(maxPoints, slopeCount[slope] + 1);
            }
        }

        return maxPoints;
    }
};