LeetCode 2152 - Minimum Number of Lines to Cover Points

LeetCode Problem 2152

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Dynamic Programming, Backtracking, Bit Manipulation, Geometry, Bitmask

Solution

Problem Understanding

This problem asks us to determine the minimum number of straight lines needed to cover a given set of points on an X-Y plane. Each point is defined by its (x, y) coordinates, and a straight line can pass through any number of points as long as they are collinear. The input is an array of unique points, and the output is an integer representing the minimum number of lines needed to cover all points.

Given the constraints, there are at most 10 points, so we are operating in a very small input space. This is important because it allows us to consider approaches that might otherwise be infeasible for larger input sizes, such as bitmask dynamic programming or exhaustive search. Edge cases to note include the possibility of all points being collinear (minimum lines = 1), points arranged so no three are collinear (maximum lines = n-1 for n points), or points with the same x or y values (vertical or horizontal lines).

Approaches

Brute Force

The brute-force approach involves checking all possible combinations of lines that could cover the points. For each subset of points that is collinear, we could try to cover the remaining points recursively. This guarantees a correct solution because it exhaustively considers all possibilities. However, the number of subsets grows exponentially with the number of points, making this approach impractical for larger inputs. Specifically, it would require checking up to 2^n subsets, and verifying collinearity for each subset adds additional computation.

Optimal Approach

The key insight for an optimal solution is that since n <= 10, we can represent sets of points using bitmasks and use dynamic programming to find the minimum number of lines. Each state in the DP represents a set of points that have already been covered. For each pair of points, we can precompute the set of all points that are collinear with that pair. Then, using DP, we iterate over all subsets of points and try to cover the remaining points with a line passing through a pair. This reduces redundant computations while guaranteeing the minimum number of lines.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n^3)	O(n)	Checks all subsets for collinearity, very slow
Optimal (Bitmask DP)	O(3^n)	O(2^n)	Uses bitmask DP to cover points efficiently

Algorithm Walkthrough

1. Precompute collinear sets: For each pair of points (i, j), calculate the bitmask representing all points collinear with this pair. Use the slope formula (y2-y1)*(x-x1) == (y-y1)*(x2-x1) to avoid floating point issues.
2. Initialize DP array: Create a DP array dp[mask] where mask is a bitmask representing covered points. Initialize dp[0] = 0 because covering no points requires zero lines.
3. Iterate over all masks: For each mask, iterate over all pairs of points (i, j) to find new points that can be covered with a single line.
4. Update DP states: For each mask and line set, calculate the new mask by OR-ing the current mask with the precomputed collinear mask. Update dp[new_mask] = min(dp[new_mask], dp[mask] + 1) to track the minimum lines needed.
5. Return the result: The answer is stored in dp[(1 << n) - 1], representing the mask where all points are covered.

Why it works: The DP explores all possible sequences of lines covering subsets of points, ensuring that every combination is considered. By always taking the minimum, it guarantees the optimal number of lines.

Python Solution

from typing import List
from itertools import combinations

class Solution:
    def minimumLines(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 1:
            return n
        
        # Precompute collinear masks
        collinear = [[0]*n for _ in range(n)]
        for i, j in combinations(range(n), 2):
            mask = 0
            x1, y1 = points[i]
            x2, y2 = points[j]
            for k, (x, y) in enumerate(points):
                if (y2 - y1) * (x - x1) == (y - y1) * (x2 - x1):
                    mask |= 1 << k
            collinear[i][j] = mask
            collinear[j][i] = mask
        
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
            first_uncovered = 0
            while first_uncovered < n and (mask >> first_uncovered) & 1:
                first_uncovered += 1
            if first_uncovered == n:
                continue
            for j in range(n):
                if j != first_uncovered:
                    new_mask = mask | collinear[first_uncovered][j]
                    dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
        
        return dp[(1 << n) - 1]

The implementation first precomputes all sets of collinear points for each pair. It then iterates through all bitmask states, attempting to cover the first uncovered point with every other point to maximize coverage. The DP ensures the minimum number of lines is calculated.

Go Solution

func minimumLines(points [][]int) int {
    n := len(points)
    if n <= 1 {
        return n
    }

    collinear := make([][]int, n)
    for i := range collinear {
        collinear[i] = make([]int, n)
    }

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            mask := 0
            x1, y1 := points[i][0], points[i][1]
            x2, y2 := points[j][0], points[j][1]
            for k := 0; k < n; k++ {
                x, y := points[k][0], points[k][1]
                if (y2-y1)*(x-x1) == (y-y1)*(x2-x1) {
                    mask |= 1 << k
                }
            }
            collinear[i][j] = mask
            collinear[j][i] = mask
        }
    }

    dp := make([]int, 1<<n)
    for i := range dp {
        dp[i] = 1 << 30
    }
    dp[0] = 0

    for mask := 0; mask < (1 << n); mask++ {
        if dp[mask] == 1<<30 {
            continue
        }
        firstUncovered := 0
        for firstUncovered < n && (mask&(1<<firstUncovered)) != 0 {
            firstUncovered++
        }
        if firstUncovered == n {
            continue
        }
        for j := 0; j < n; j++ {
            if j != firstUncovered {
                newMask := mask | collinear[firstUncovered][j]
                if dp[newMask] > dp[mask]+1 {
                    dp[newMask] = dp[mask] + 1
                }
            }
        }
    }

    return dp[(1<<n)-1]
}

In Go, we handle slices and bitmask operations similarly to Python. We initialize a large number to represent infinity and iterate over all bitmask states. The logic is identical to the Python version.

Worked Examples

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

Mask (binary)	First Uncovered	Pair	New Mask	DP Value
0000	0	(0,1)	0111	1
0111	3	(3, any)	1111	2

Final answer: 2

Example 2: points = [[0,2],[-2,-2],[1,4]]

All points are collinear through (-2,-2) and (1,4), so DP directly covers all points in one line.

Final answer: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(3^n)	Each mask iteration can branch to up to n states for first uncovered, generating exponential combinations.
Space	O(2^n)	The DP array stores values for all subsets of points.

The 3^n time comes from the subset DP branching, which is feasible given n <= 10.

Test Cases

# Provided examples
assert Solution().minimumLines([[0,1],[2,3],[4,5],[4,3]]) == 2  # Mixed collinear sets
assert Solution().minimumLines([[0,2],[-2,-2],[1,4]]) == 1     # All points collinear

# Single point
assert Solution().minimumLines([[0,0]]) == 1

# Two points
assert Solution().minimumLines([[1,1],[2,2]]) == 1

# No three collinear points