Minimum Number of Lines to Cover Points — DSA

Problem#

Return the minimum number of straight lines that pass through all given 2D points (lines may be of any slope, and a line through only one point still counts as a line).

Examples#

[[0,1],[2,3],[4,5],[4,3]] → 2.
[[0,2],[-2,-2],[1,4]] → 1.

Constraints#

1 <= points.length <= 10.

Approach#

With n <= 10, bitmask DP. State: set of uncovered points. For each state, pick the lowest-indexed uncovered point and try pairing it with every other uncovered point to define a line; clear all collinear-on-that-line bits.

Solution#

class Solution {
public:
    int minimumLines(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) return 1;
        // collinear[i] = bitmask of points collinear with the line through points i and any j (j set elsewhere)
        auto cross = [&](int a, int b, int c) {
            long long x1 = points[b][0] - points[a][0], y1 = points[b][1] - points[a][1];
            long long x2 = points[c][0] - points[a][0], y2 = points[c][1] - points[a][1];
            return x1 * y2 - y1 * x2;
        };
        vector<vector<int>> lineMask(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j) {
                int m = (1 << i) | (1 << j);
                for (int k = 0; k < n; ++k)
                    if (k != i && k != j && cross(i, j, k) == 0)
                        m |= (1 << k);
                lineMask[i][j] = lineMask[j][i] = m;
            }
        int FULL = (1 << n) - 1;
        vector<int> dp(1 << n, INT_MAX / 2);
        dp[0] = 0;
        for (int s = 0; s < (1 << n); ++s) {
            if (dp[s] == INT_MAX / 2) continue;
            if (s == FULL) continue;
            // find lowest uncovered point
            int i = __builtin_ctz(~s & FULL);
            // option 1: line through just i
            int ns = s | (1 << i);
            dp[ns] = min(dp[ns], dp[s] + 1);
            // option 2: line through i and any other uncovered j
            for (int j = 0; j < n; ++j)
                if (j != i && !((s >> j) & 1)) {
                    int t = s | lineMask[i][j];
                    dp[t] = min(dp[t], dp[s] + 1);
                }
        }
        return dp[FULL];
    }
};

func minimumLines(points [][]int) int {
    n := len(points)
    if n <= 2 {
        return 1
    }
    cross := func(a, b, c int) int64 {
        x1 := int64(points[b][0] - points[a][0])
        y1 := int64(points[b][1] - points[a][1])
        x2 := int64(points[c][0] - points[a][0])
        y2 := int64(points[c][1] - points[a][1])
        return x1*y2 - y1*x2
    }
    lineMask := make([][]int, n)
    for i := range lineMask {
        lineMask[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            m := (1 << i) | (1 << j)
            for k := 0; k < n; k++ {
                if k != i && k != j && cross(i, j, k) == 0 {
                    m |= 1 << k
                }
            }
            lineMask[i][j] = m
            lineMask[j][i] = m
        }
    }
    FULL := (1 << n) - 1
    INF := math.MaxInt32 / 2
    dp := make([]int, 1<<n)
    for i := range dp {
        dp[i] = INF
    }
    dp[0] = 0
    for s := 0; s < (1 << n); s++ {
        if dp[s] >= INF {
            continue
        }
        if s == FULL {
            continue
        }
        free := ^s & FULL
        i := 0
        for free&(1<<i) == 0 {
            i++
        }
        ns := s | (1 << i)
        if dp[s]+1 < dp[ns] {
            dp[ns] = dp[s] + 1
        }
        for j := 0; j < n; j++ {
            if j != i && (s>>j)&1 == 0 {
                t := s | lineMask[i][j]
                if dp[s]+1 < dp[t] {
                    dp[t] = dp[s] + 1
                }
            }
        }
    }
    return dp[FULL]
}

from typing import List

class Solution:
    def minimumLines(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return 1

        def cross(a: int, b: int, c: int) -> int:
            x1 = points[b][0] - points[a][0]
            y1 = points[b][1] - points[a][1]
            x2 = points[c][0] - points[a][0]
            y2 = points[c][1] - points[a][1]
            return x1 * y2 - y1 * x2

        line_mask = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                m = (1 << i) | (1 << j)
                for k in range(n):
                    if k != i and k != j and cross(i, j, k) == 0:
                        m |= 1 << k
                line_mask[i][j] = m
                line_mask[j][i] = m

        FULL = (1 << n) - 1
        INF = float('inf')
        dp = [INF] * (1 << n)
        dp[0] = 0
        for s in range(1 << n):
            if dp[s] == INF or s == FULL:
                continue
            free = ~s & FULL
            i = (free & -free).bit_length() - 1
            ns = s | (1 << i)
            if dp[s] + 1 < dp[ns]:
                dp[ns] = dp[s] + 1
            for j in range(n):
                if j != i and not ((s >> j) & 1):
                    t = s | line_mask[i][j]
                    if dp[s] + 1 < dp[t]:
                        dp[t] = dp[s] + 1
        return dp[FULL]

function minimumLines(points) {
    const n = points.length;
    if (n <= 2) return 1;
    const cross = (a, b, c) => {
        const x1 = points[b][0] - points[a][0];
        const y1 = points[b][1] - points[a][1];
        const x2 = points[c][0] - points[a][0];
        const y2 = points[c][1] - points[a][1];
        return x1 * y2 - y1 * x2;
    };
    const lineMask = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let m = (1 << i) | (1 << j);
            for (let k = 0; k < n; k++) {
                if (k !== i && k !== j && cross(i, j, k) === 0) m |= 1 << k;
            }
            lineMask[i][j] = m;
            lineMask[j][i] = m;
        }
    }
    const FULL = (1 << n) - 1;
    const INF = Infinity;
    const dp = new Array(1 << n).fill(INF);
    dp[0] = 0;
    for (let s = 0; s < (1 << n); s++) {
        if (dp[s] === INF || s === FULL) continue;
        const free = ~s & FULL;
        let i = 0;
        while ((free & (1 << i)) === 0) i++;
        const ns = s | (1 << i);
        if (dp[s] + 1 < dp[ns]) dp[ns] = dp[s] + 1;
        for (let j = 0; j < n; j++) {
            if (j !== i && ((s >> j) & 1) === 0) {
                const t = s | lineMask[i][j];
                if (dp[s] + 1 < dp[t]) dp[t] = dp[s] + 1;
            }
        }
    }
    return dp[FULL];
}

class Solution {
    private int[][] pts;

    public int minimumLines(int[][] points) {
        int n = points.length;
        if (n <= 2) return 1;
        pts = points;
        int[][] lineMask = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int m = (1 << i) | (1 << j);
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j && cross(i, j, k) == 0) m |= 1 << k;
                }
                lineMask[i][j] = m;
                lineMask[j][i] = m;
            }
        }
        int FULL = (1 << n) - 1;
        int INF = Integer.MAX_VALUE / 2;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int s = 0; s < (1 << n); s++) {
            if (dp[s] >= INF || s == FULL) continue;
            int free = ~s & FULL;
            int i = Integer.numberOfTrailingZeros(free);
            int ns = s | (1 << i);
            if (dp[s] + 1 < dp[ns]) dp[ns] = dp[s] + 1;
            for (int j = 0; j < n; j++) {
                if (j != i && ((s >> j) & 1) == 0) {
                    int t = s | lineMask[i][j];
                    if (dp[s] + 1 < dp[t]) dp[t] = dp[s] + 1;
                }
            }
        }
        return dp[FULL];
    }

    private long cross(int a, int b, int c) {
        long x1 = pts[b][0] - pts[a][0];
        long y1 = pts[b][1] - pts[a][1];
        long x2 = pts[c][0] - pts[a][0];
        long y2 = pts[c][1] - pts[a][1];
        return x1 * y2 - y1 * x2;
    }
}

function minimumLines(points: number[][]): number {
    const n = points.length;
    if (n <= 2) return 1;
    const cross = (a: number, b: number, c: number): number => {
        const x1 = points[b][0] - points[a][0];
        const y1 = points[b][1] - points[a][1];
        const x2 = points[c][0] - points[a][0];
        const y2 = points[c][1] - points[a][1];
        return x1 * y2 - y1 * x2;
    };
    const lineMask: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let m = (1 << i) | (1 << j);
            for (let k = 0; k < n; k++) {
                if (k !== i && k !== j && cross(i, j, k) === 0) m |= 1 << k;
            }
            lineMask[i][j] = m;
            lineMask[j][i] = m;
        }
    }
    const FULL = (1 << n) - 1;
    const INF = Infinity;
    const dp: number[] = new Array(1 << n).fill(INF);
    dp[0] = 0;
    for (let s = 0; s < (1 << n); s++) {
        if (dp[s] === INF || s === FULL) continue;
        const free = ~s & FULL;
        let i = 0;
        while ((free & (1 << i)) === 0) i++;
        const ns = s | (1 << i);
        if (dp[s] + 1 < dp[ns]) dp[ns] = dp[s] + 1;
        for (let j = 0; j < n; j++) {
            if (j !== i && ((s >> j) & 1) === 0) {
                const t = s | lineMask[i][j];
                if (dp[s] + 1 < dp[t]) dp[t] = dp[s] + 1;
            }
        }
    }
    return dp[FULL];
}

Editorial#

With n <= 10 we can afford 2^n states. Fixing the lowest-uncovered point per state breaks symmetry (any line we add must cover it), so we only enumerate O(n) candidate lines per state — total O(2^n n^2). Cross-product collinearity avoids float pitfalls.

Complexity#

Time: O(2^n * n^2).
Space: O(2^n).

Concept revision#

Max Points on a Line