Skip to main content
Talentd

Minimum Number of Lines to Cover Points - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableMathDynamic Programming6 min readAsked at: Morgan Stanley
Practice this problem

Problem Statement

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 <= 10
  • points[i].length == 2
  • -100 <= xi, yi <= 100
  • All the points are 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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Collinearity ChecksO(n! * n)O(n)Conceptual baseline or when demonstrating brute-force reasoning
Precomputed Lines + Bitmask DPO(n^2 * 2^n)O(2^n)Optimal solution for small n (≤10) using subset dynamic programming

Video Solution

2152. Minimum Number of Lines to Cover Points • Shuo Yan • 362 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Number of Lines to Cover Points with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Points on a Line

Next

Min Cost to Connect All Points