Minimum Number of Lines to Cover Points - Practice Coding Problems

Minimum Number of Lines to Cover Points - Problem

Array Hash Table Math Dynamic Programming Backtracking Bit Manipulation Geometry Bitmask Medium

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 & Output

Example 1 — Basic Case

$ Input: points = [[1,1],[2,2],[3,4],[4,5],[5,5]]

› Output: 3

💡 Note: One possible solution: Line 1 passes through (1,1) and (2,2); Line 2 passes through (3,4) and (4,5); Line 3 passes through (5,5). Total: 3 lines.

Example 2 — Collinear Points

$ Input: points = [[1,1],[2,2],[3,3],[4,4]]

› Output: 1

💡 Note: All points are collinear (on the line y=x), so only 1 line is needed to cover all points.

Example 3 — Minimum Case

$ Input: points = [[1,1],[2,3]]

› Output: 1

💡 Note: Any two points can be covered by exactly one line.

Constraints

1 ≤ points.length ≤ 20
points[i].length == 2
-100 ≤ points[i][0], points[i][1] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given points scattered on 2D plane

Find Lines

Identify optimal lines that cover multiple points

Count Lines

Return minimum number of lines needed

Key Takeaway

🎯 Key Insight: Group collinear points together to minimize the total number of lines needed

Asked in

G Google 15 f Meta 12 a Amazon 8

This problem requires finding the minimum number of straight lines to cover all points. The key insight is that collinear points can share the same line. The optimal approach uses dynamic programming with bitmasks to track covered points efficiently. Time: O(2ⁿ × n²), Space: O(2ⁿ).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(2ⁿ × n³)	O(n)	Try all possible combinations of lines to find minimum
Dynamic Programming with Bitmask	O(2ⁿ × n²)	O(2ⁿ)	Use DP with bitmask to efficiently track covered points

Brute Force with Backtracking — Algorithm Steps

Generate all possible lines from pairs of points
Use backtracking to try different line combinations
Track minimum number of lines needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Lines

Create all possible lines from point pairs

Backtrack

Try different combinations of lines

Find Minimum

Return the minimum number of lines needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int areCollinear(int* p1, int* p2, int* p3) {
    return (p2[1] - p1[1]) * (p3[0] - p1[0]) == (p3[1] - p1[1]) * (p2[0] - p1[0]);
}

int* getLinePoints(int i, int j, int** points, int n, int* count) {
    int* linePoints = malloc(n * sizeof(int));
    linePoints[0] = i;
    linePoints[1] = j;
    *count = 2;
    
    for (int k = 0; k < n; k++) {
        if (k != i && k != j && areCollinear(points[i], points[j], points[k])) {
            linePoints[(*count)++] = k;
        }
    }
    return linePoints;
}

int backtrack(int** points, int n, int covered, int linesUsed, int* minLines) {
    if (covered == (1 << n) - 1) {
        return linesUsed;
    }
    
    if (linesUsed >= *minLines) {
        return INT_MAX;
    }
    
    int result = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (covered & (1 << i)) continue;
        for (int j = i + 1; j < n; j++) {
            if (covered & (1 << j)) continue;
            
            int count;
            int* linePoints = getLinePoints(i, j, points, n, &count);
            int newCovered = covered;
            for (int k = 0; k < count; k++) {
                newCovered |= (1 << linePoints[k]);
            }
            
            int subResult = backtrack(points, n, newCovered, linesUsed + 1, minLines);
            if (subResult != INT_MAX && subResult < result) {
                result = subResult;
            }
            
            free(linePoints);
        }
    }
    
    return result;
}

int solution(int** points, int n) {
    if (n <= 2) return n > 0 ? 1 : 0;
    
    int minLines = n;
    return backtrack(points, n, 0, 0, &minLines);
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    // Simple parsing for points array
    int** points = malloc(20 * sizeof(int*));
    int n = 0;
    
    char* token = strtok(input, "[]");
    while (token != NULL) {
        if (strchr(token, ',') && !strchr(token, ']')) {
            int* point = malloc(2 * sizeof(int));
            sscanf(token, "%d,%d", &point[0], &point[1]);
            points[n++] = point;
        }
        token = strtok(NULL, "[]");
    }
    
    int result = solution(points, n);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(points[i]);
    }
    free(points);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n³)

Exponential combinations of point subsets, with O(n³) work to check collinearity

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and temporary storage for current solution

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler