LeetCode Solutions Blog

Minimum Number of Lines to Cover Points

Number: 2287

Difficulty: Medium

Paid? Yes

Problem Description

Given an array of unique points on the X-Y plane, determine the minimum number of straight lines required such that every point is intersected (or covered) by at least one of these lines. Each line may cover more than two points if they are collinear.

Key Insights

The number of points is small (up to 10), which permits a solution using bitmask dynamic programming (DP) to explore all subsets.
Two points are always collinear; the challenge is to exploit the fact that a line defined by two points might cover additional points.
Precomputing, for every pair of points, a bitmask representing all points on the same line helps reduce repeated computations.
Use recursion with state represented as a bitmask to cover the remaining points with the fewest lines.
For each DP state, pick an uncovered point and try to cover as many additional points as possible by drawing a line through it and another uncovered point.

Space and Time Complexity

Time Complexity: O(2^n * n^2) where n is the number of points (since n is at most 10, this is acceptable).
Space Complexity: O(2^n) for the DP memoization.

Solution

The solution uses a bitmask DP approach where each bit in the mask represents whether a point has been covered by a line. Initially, no points are covered (mask=0). We pick the first uncovered point and try pairing it with every other uncovered point to form a line. For each pair, we compute a bitmask of all points that lie on the line defined by these two points. Then we recursively solve for the new state after covering those points.
Important steps include:

Checking collinearity using the cross product method.
Precomputing the "line mask" for each pair of points.
Using recursion (or iterative DP) with memoization to decide the optimal set of lines that covers all points.

Code Solutions

Below are the solutions in Python, JavaScript, C++, and Java.

# Python solution using bitmask DP and recursion with memoization

def minLines(points):
    n = len(points)
    if n <= 1:
        return n  # If there's 0 or 1 point, we need at most 1 line

    # Function to check if three points are collinear using cross product
    def collinear(i, j, k):
        # (y[j]-y[i])*(x[k]-x[i]) == (x[j]-x[i])*(y[k]-y[i])
        return (points[j][1] - points[i][1]) * (points[k][0] - points[i][0]) == \
               (points[j][0] - points[i][0]) * (points[k][1] - points[i][1])
    
    # Precompute line masks for every pair of points
    line_mask = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            mask = (1 << i) | (1 << j)
            for k in range(n):
                if k != i and k != j and collinear(i, j, k):
                    mask |= (1 << k)
            line_mask[i][j] = mask

    full_mask = (1 << n) - 1
    dp = {}

    # dp(covered) returns the minimum number of lines needed after covering points represented by 'covered'
    def solve(covered):
        if covered == full_mask:
            return 0  # All points are covered
        if covered in dp:
            return dp[covered]
        
        # Find first uncovered point
        for i in range(n):
            if not (covered & (1 << i)):
                first_uncovered = i
                break

        res = float('inf')
        # If the only uncovered point left, one line is enough.
        # Else, try pairing first_uncovered with every other uncovered point.
        for j in range(first_uncovered + 1, n):
            if not (covered & (1 << j)):
                new_covered = covered | line_mask[first_uncovered][j]
                res = min(res, 1 + solve(new_covered))
        # Also consider drawing a single line to cover the lone point if needed.
        dp[covered] = res if res != float('inf') else 1
        return dp[covered]

    return solve(0)

# Example usage:
points1 = [[0,1],[2,3],[4,5],[4,3]]
print(minLines(points1))  # Expected output: 2