Minimum Number of Lines to Cover Points solution and explanation
The problem
You are given an array points where points[i] = [xi, yi] represents a point on an X-Y plane.
Straight lines are going to be added to the X-Y plane, such that every point is covered by at least one line.
Return the minimum number of straight lines needed to cover all the points.
Example 1:
Input: points = [[0,1],[2,3],[4,5],[4,3]] Output: 2 Explanation: The minimum number of straight lines needed is two. One possible solution is to add: - One line connecting the point at (0, 1) to the point at (4, 5). - Another line connecting the point at (2, 3) to the point at (4, 3).
Example 2:
Input: points = [[0,2],[-2,-2],[1,4]] Output: 1 Explanation: The minimum number of straight lines needed is one. The only solution is to add: - One line connecting the point at (-2, -2) to the point at (1, 4).
Constraints:
1 <= points.length <= 10points[i].length == 2-100 <= xi, yi <= 100- All the
pointsare unique.
Approach overview
Problem Overview: You receive a list of 2D points. A single straight line can cover any number of points if they are collinear. The task is to cover every point using the minimum number of lines.
The constraint is small (typically ≤10 points), which hints that exponential techniques like bit manipulation and subset dynamic programming are practical. The key challenge is efficiently determining which subsets of points lie on the same line.
Approach 1: Backtracking with Collinearity Checks (Exponential)
This approach recursively tries to draw lines through pairs of points and marks all collinear points as covered. At each step, pick an uncovered point and attempt lines formed with every other point. All points that satisfy the slope equation are included in the same line. Continue recursively until all points are covered.
The algorithm repeatedly checks whether three points are collinear using the cross-product condition. While straightforward, it recomputes many states and explores redundant configurations. Time complexity grows roughly O(n! * n) in the worst case with O(n) space for recursion, making it impractical without pruning.
Approach 2: Precompute Lines + Bitmask Dynamic Programming (Optimal)
This approach models the problem as covering a set of points using the minimum number of line subsets. Represent the set of points with a bitmask where bit i indicates whether point i is covered. For every pair of points, compute a mask containing all points that lie on the same line using a geometry collinearity test.
Once these line masks are prepared, apply DP over subsets. Let dp[mask] represent the minimum number of lines required to cover the points represented by mask. For each state, pick the first uncovered point and try every precomputed line passing through it. Transition to a new mask by marking all points on that line as covered.
This reduces the search space dramatically because each line operation covers multiple points at once. Precomputation takes O(n^3) time, and the DP over subsets takes about O(n^2 * 2^n) time with O(2^n) space. The method combines dynamic programming, bitmasking, and basic geometry concepts.
Recommended for interviews: The bitmask DP approach is what interviewers expect. Starting with the brute-force backtracking explanation shows you understand the search space. Transitioning to subset DP with precomputed collinear masks demonstrates strong optimization skills and familiarity with small-constraint exponential problems.
Solution
class Solution:
def minimumLines(self, points: List[List[int]]) -> int:
def check(i, j, k):
x1, y1 = points[i]
x2, y2 = points[j]
x3, y3 = points[k]
return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1)
@cache
def dfs(state):
if state == (1 << n) - 1:
return 0
ans = inf
for i in range(n):
if not (state >> i & 1):
for j in range(i + 1, n):
nxt = state | 1 << i | 1 << j
for k in range(j + 1, n):
if not (nxt >> k & 1) and check(i, j, k):
nxt |= 1 << k
ans = min(ans, dfs(nxt) + 1)
if i == n - 1:
ans = min(ans, dfs(state | 1 << i) + 1)
return ans
n = len(points)
return dfs(0)class Solution {
private int[] f;
private int[][] points;
private int n;
public int minimumLines(int[][] points) {
n = points.length;
this.points = points;
f = new int[1 << n];
return dfs(0);
}
private int dfs(int state) {
if (state == (1 << n) - 1) {
return 0;
}
if (f[state] != 0) {
return f[state];
}
int ans = 1 << 30;
for (int i = 0; i < n; ++i) {
if (((state >> i) & 1) == 0) {
for (int j = i + 1; j < n; ++j) {
int nxt = state | 1 << i | 1 << j;
for (int k = j + 1; k < n; ++k) {
if (((state >> k) & 1) == 0 && check(i, j, k)) {
nxt |= 1 << k;
}
}
ans = Math.min(ans, dfs(nxt) + 1);
}
if (i == n - 1) {
ans = Math.min(ans, dfs(state | 1 << i) + 1);
}
}
}
return f[state] = ans;
}
private boolean check(int i, int j, int k) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int x3 = points[k][0], y3 = points[k][1];
return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);
}
}class Solution {
public:
int minimumLines(vector<vector<int>>& points) {
auto check = [&](int i, int j, int k) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int x3 = points[k][0], y3 = points[k][1];
return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);
};
int n = points.size();
int f[1 << n];
memset(f, 0, sizeof f);
function<int(int)> dfs = [&](int state) -> int {
if (state == (1 << n) - 1) return 0;
if (f[state]) return f[state];
int ans = 1 << 30;
for (int i = 0; i < n; ++i) {
if (!(state >> i & 1)) {
for (int j = i + 1; j < n; ++j) {
int nxt = state | 1 << i | 1 << j;
for (int k = j + 1; k < n; ++k) {
if (!(nxt >> k & 1) && check(i, j, k)) {
nxt |= 1 << k;
}
}
ans = min(ans, dfs(nxt) + 1);
}
if (i == n - 1) {
ans = min(ans, dfs(state | 1 << i) + 1);
}
}
}
return f[state] = ans;
};
return dfs(0);
}
};func minimumLines(points [][]int) int {
check := func(i, j, k int) bool {
x1, y1 := points[i][0], points[i][1]
x2, y2 := points[j][0], points[j][1]
x3, y3 := points[k][0], points[k][1]
return (x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)
}
n := len(points)
f := make([]int, 1<<n)
var dfs func(int) int
dfs = func(state int) int {
if state == (1<<n)-1 {
return 0
}
if f[state] > 0 {
return f[state]
}
ans := 1 << 30
for i := 0; i < n; i++ {
if (state >> i & 1) == 0 {
for j := i + 1; j < n; j++ {
nxt := state | 1<<i | 1<<j
for k := j + 1; k < n; k++ {
if (nxt>>k&1) == 0 && check(i, j, k) {
nxt |= 1 << k
}
}
ans = min(ans, dfs(nxt)+1)
}
if i == n-1 {
ans = min(ans, dfs(state|1<<i)+1)
}
}
}
f[state] = ans
return ans
}
return dfs(0)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Collinearity Checks | O(n! * n) | O(n) | Conceptual baseline or when demonstrating brute-force reasoning |
| Precomputed Lines + Bitmask DP | O(n^2 * 2^n) | O(2^n) | Optimal solution for small n (≤10) using subset dynamic programming |
Frequently asked questions
Is Minimum Number of Lines to Cover Points easy or hard?
This problem is rated Medium but feels closer to Hard if you are unfamiliar with subset dynamic programming. The difficulty comes from recognizing that small input size allows bitmask DP and from efficiently precomputing collinear point sets.
Minimum Number of Lines to Cover Points Python/Java solution
Implementations typically compute line masks using nested loops and store them in an array. A DP array of size 2^n tracks the minimum lines required for each subset. The same logic works across Python, Java, C++, and Go because the algorithm relies mainly on bit operations and simple geometry checks.
How to solve Minimum Number of Lines to Cover Points in O(n^2 * 2^n)?
First compute a bitmask for every pair of points representing all points that lie on the same line. Then run dynamic programming over subsets where dp[mask] stores the minimum lines needed to cover that subset. For each state, select an uncovered point and try all lines passing through it to update the DP state.
What is the best approach for Minimum Number of Lines to Cover Points?
The most efficient solution uses bitmask dynamic programming with precomputed collinear point sets. Each subset of points is represented by a bitmask, and DP transitions simulate drawing a line that covers multiple points at once. This reduces the search space significantly compared to brute-force recursion and runs in O(n^2 * 2^n) time.
Is Minimum Number of Lines to Cover Points asked at Google/Amazon/Meta?
Problems combining geometry with bitmask dynamic programming frequently appear in interviews at companies like Google and Meta. They test the ability to model a geometric constraint as a subset DP problem and optimize brute-force search using bitmasks.
What data structure is used in Minimum Number of Lines to Cover Points?
The solution relies on bitmasks to represent subsets of points and a DP array to store results for each subset. Basic geometry calculations are used to test whether three points are collinear. Arrays and bit operations are the core data structures involved.
What is the time complexity of Minimum Number of Lines to Cover Points?
The optimal approach runs in O(n^2 * 2^n) time with O(2^n) space. The algorithm first precomputes which points lie on the same line and stores them as bitmasks. Then dynamic programming iterates over all subsets of points to compute the minimum number of lines required.