Coding

Minimum Number of Lines to Cover Points

Asked at

BharatPe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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.

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).

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).

Consider the input **points = [[1, 2], [3, 4], [5, 6], [7, 8]]. **How many lines are required to cover all points?

1 <= points.length <= 10
points[i].length == 2
-100 <= xi, y****i <= 100
All the points are unique.

cpp

class Solution {
public:
    int minimumLines(vector<vector<int>>& points) {
        // Your code goes here
    }
};

java

class Solution {
    public int minimumLines(int[][] points) {
        // Your code goes here
    }
}

python

class Solution:
    def minimumLines(self, points):
        # Your code goes here

javascript

class Solution {
    minimumLines(points) {
        // Your code goes here
    }
}

csharp

public class Solution{
      
    public int MinimumLines(List<int[]> points){
            // Your code goes here
    }
}

func minimumLines(points [][]int) int {
}

Stuck? Show a way to structure it+

01Precompute the mask covered by every line through a pair of points.
02Let dp(mask) be minimum lines covering selected points.
03Choose the first uncovered point.
04Try every line through it and recurse on the union mask.
05Memoize states.

Reference answer

This problem is tractable when the number of points is small. Precompute a bitmask for every line determined by two points, adding every point collinear with that pair; also include a singleton mask for each point. Let solve(mask) be the minimum extra lines needed after mask points are covered. Pick the first uncovered point i; any optimal next line can be assumed to cover i, so try every precomputed line containing it and minimize 1 + solve(mask | lineMask). Memoization visits at most 2^N masks, with an O(N^2) choice factor after precomputation. Use cross products, not floating-point slopes, for collinearity: (x2-x1)*(y3-y1) == (y2-y1)*(x3-x1). This is O(2^N*N^2) time and O(2^N) space.

Then expect these follow-ups

How would you recover the chosen lines?
Tests: DP reconstruction
Why is choosing the first uncovered point safe?
Tests: optimal substructure

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question