LeetCode 149: Max Points on a Line Solution in Python Explained

Problem Statement

In LeetCode 149, you’re given an array points where points[i] = [xi, yi] represents a point on a 2D plane. Your task is to return the maximum number of points that lie on the same straight line. This differs from linked list sorting like LeetCode 148: Sort List, focusing on geometric alignment rather than order.

Constraints

• 1 <= points.length <= 300
• points[i].length == 2
• -10^4 <= xi, yi <= 10^4
• All points are unique

Example

Let’s see some cases:

Copy codeInput: points = [[1,1],[2,2],[3,3]]
Output: 3
Explanation: All points (1,1), (2,2), (3,3) lie on the line y = x.

Copy codeInput: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: Points (1,1), (5,3), (4,1), (2,3) lie on the line y = (2/3)x + 1/3.

Copy codeInput: points = [[1,1]]
Output: 1
Explanation: Single point, trivially on a line.

These examples show we’re finding the max collinear points.

Understanding the Problem

How do you solve LeetCode 149: Max Points on a Line in Python? Take points = [[1,1],[2,2],[3,3]]. All three points are collinear (slope = 1), so return 3. For [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]], four points align on a line (slope 2/3), so return 4. This isn’t a cache problem like LeetCode 146: LRU Cache; it’s about geometry and slopes. We’ll use: 1. Hash Map with Slope Counting: O(n²) time, O(n) space—our best solution. 2. Brute Force Pairwise Slope: O(n³) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Hash Map with Slope Counting Approach

Explanation

Hash Map with Slope Counting iterates over each point as a reference, calculating slopes to all other points and using a hash map to count points with the same slope. For each reference point:

• Compute slopes, handling vertical lines and duplicates.
• Track the max count per slope, adding duplicates.
• Update the global maximum.

This is the best solution due to its O(n²) time complexity (optimal for this problem), O(n) space, and efficient slope tracking, balancing speed and clarity.

For [[1,1],[2,2],[3,3]]:

• From (1,1): slopes to (2,2) and (3,3) are 1, count = 3.
• Max = 3.

Step-by-Step Example

Example 1: points = [[1,1],[2,2],[3,3]]

Goal: Return 3.

• Start: max_points = 0.
• Step 1: Reference (1,1).
• Slope to (2,2): (2-1)/(2-1) = 1, slopes = {1:1{.
• Slope to (3,3): (3-1)/(3-1) = 1, slopes = {1:2{.
• Local max = 1 (self) + 2 (slopes[1]) = 3.
• max_points = 3.
• Step 2: Reference (2,2).
• Slope to (1,1), (3,3): 1, count = 3, max_points = 3.
• Step 3: Reference (3,3).
• Same slope, count = 3, max_points = 3.
• Finish: Return 3.

Example 2: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Goal: Return 4.

• Step 1: Reference (1,1).
• Slopes: (3,2) = 1/2, (5,3) = 2/3, (4,1) = 0, (2,3) = 2, (1,4) = inf.
• slopes = {1/2:1, 2/3:1, 0:1, 2:1, inf:1{, local max = 1+1 = 2, max_points = 2.
• Step 2: Reference (5,3).
• Slopes: (1,1) = 2/3, (3,2) = 1/2, (4,1) = 2, (2,3) = 0, (1,4) = -1/4.
• Local max = 2 (with (1,1)), max_points = 2.
• Step 3: After checking all, (1,1), (5,3), (4,1), (2,3) align (slope 2/3), max_points = 4.
• Finish: Return 4.

Example 3: points = [[1,1]]

Goal: Return 1.

• Start: Single point, return 1.
• Finish: Return 1.

How the Code Works (Hash Map with Slope Counting) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef maxPoints(points: list[list[int]]) -> int:
    # Line 1: Handle base cases
    if len(points) <= 2:
        # If 0, 1, or 2 points (e.g., [[1,1]]), all collinear
        return len(points)

    # Line 2: Initialize global maximum
    max_points = 0
    # Tracks max collinear points (e.g., initially 0)

    # Line 3: Iterate over each point as reference
    for i in range(len(points)):
        # i = reference point index (e.g., 0 for [1,1])

        # Line 4: Initialize slope hash map and duplicates
        slopes = { {
        # Maps slope to count (e.g., {1:2{)
        duplicates = 0
        # Counts points identical to reference (e.g., 0)

        # Line 5: Calculate slopes to other points
        x1, y1 = points[i]
        # Reference point (e.g., (1,1))
        for j in range(i + 1, len(points)):
            # j = other point index (e.g., 1 for [2,2])
            x2, y2 = points[j]
            # Other point (e.g., (2,2))

            # Line 6: Handle duplicates
            if x1 == x2 and y1 == y2:
                # If same point (not applicable here, but possible)
                duplicates += 1
                continue

            # Line 7: Calculate slope
            dx = x2 - x1
            # Delta x (e.g., 2-1=1)
            dy = y2 - y1
            # Delta y (e.g., 2-1=1)
            if dx == 0:
                # Vertical line (e.g., inf)
                slope = float('inf')
            else:
                # Slope = dy/dx (e.g., 1/1=1.0)
                slope = dy / dx

            # Line 8: Update slope count
            slopes[slope] = slopes.get(slope, 0) + 1
            # Increment count (e.g., {1:1{, then {1:2{)

        # Line 9: Update max points from slopes
        if slopes:
            # If slopes exist (e.g., {1:2{)
            max_points = max(max_points, max(slopes.values()) + duplicates + 1)
            # Max of current max or slope count + duplicates + self
            # e.g., max(0, 2+0+1) = 3
        else:
            # Only duplicates (e.g., single point case)
            max_points = max(max_points, duplicates + 1)
            # e.g., 1 for [[1,1]]

    # Line 10: Return maximum collinear points
    return max_points
    # Final result (e.g., 3)

This detailed breakdown clarifies how the hash map with slope counting efficiently finds the maximum collinear points.

Alternative: Brute Force Pairwise Slope Approach

Explanation

Brute Force Pairwise Slope checks every triplet of points, calculating if they’re collinear by comparing slopes between pairs (e.g., slope AB = slope BC). It’s a practical alternative, simple to understand, but O(n³) time makes it less efficient, using O(1) space.

For [[1,1],[2,2],[3,3]]:

• Check (1,1),(2,2),(3,3): Slope 1 = 1, collinear, count = 3.

Step-by-Step Example (Alternative)

For [[1,1],[2,2],[3,3]]:

• Step 1: Triplet (1,1),(2,2),(3,3).
• Slope (1,1)-(2,2) = 1, (2,2)-(3,3) = 1, collinear, count = 3.
• Step 2: All triplets confirm 3.
• Finish: Return 3.

How the Code Works (Brute Force)

Copy codedef maxPointsBrute(points: list[list[int]]) -> int:
    if len(points) <= 2:
        return len(points)
    max_points = 0
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            count = 2
            x1, y1 = points[i]
            x2, y2 = points[j]
            for k in range(j+1, len(points)):
                x3, y3 = points[k]
                if (y2-y1)*(x3-x2) == (y3-y2)*(x2-x1):  # Cross-multiply slopes
                    count += 1
            max_points = max(max_points, count)
    return max_points

Complexity

• Hash Map with Slope Counting:
• Time: O(n²) – n reference points, n slopes each.
• Space: O(n) – hash map.
• Brute Force Pairwise Slope:
• Time: O(n³) – triplets checked.
• Space: O(1) – constant space.

Efficiency Notes

Hash Map with Slope Counting is the best solution with O(n²) time and O(n) space, offering optimal efficiency for this problem—Brute Force Pairwise Slope uses O(n³) time, making it simpler but significantly slower, though space-efficient.

Key Insights

• Slopes: Key to collinearity.
• Hash Map: Counts efficiently.
• Brute Force: Checks all triplets.

Additional Example

For points = [[0,0],[1,1],[0,1]]:

• Goal: 2.
• Hash Map: Max slope count = 2 (e.g., vertical).

Edge Cases

• Single Point: [[1,1]] → 1.
• Two Points: [[1,1],[2,2]] → 2.
• Vertical Line: [[1,1],[1,2],[1,3]] → 3.

Both solutions handle these well.

Final Thoughts

LeetCode 149: Max Points on a Line in Python is a challenging geometric puzzle. The Hash Map with Slope Counting solution excels with its efficiency and clarity, while Brute Force Pairwise Slope offers a straightforward approach. Want more? Try LeetCode 148: Sort List for list sorting or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 149 on LeetCode with [[1,1],[2,2],[3,3]], aiming for 3—test your skills now!