2152. Minimum Number of Lines to Cover Points

MediumBit ManipulationGeometryArrayHash TableMathDynamic ProgrammingBacktrackingBitmask
Leetcode Link

Problem Description

In this problem, we're presented with a set of coordinates, points, where each element points[i] is an array containing the x and y coordinates [x_i, y_i] of a point on a 2D plane. The challenge is to determine the minimum number of straight lines that are necessary to ensure that each point in the array is covered by at least one line.

A key detail to note is that a single straight line can cover multiple points if those points are all collinear, that is, they lie on the same straight line.

Intuition

The intuition behind solving this problem involves a geometric understanding of points and lines. Two points define a unique line. But if we have three or more points, we must check whether they are collinear. If they are, a single line can cover them all.

The solution approach leans on combinatorial optimization and uses depth-first search (DFS) with bitwise state representation and memoization to reduce redundant calculations. We use a state variable to represent the set of points that have already been covered by lines. When all points are covered, the state would equal 2^n - 1, where n is the number of points, as each bit in the state represents whether a corresponding point is covered or not.

To check whether three points are collinear, we use the cross product formula. For points i, j, and k, the intuition is to compare the slopes between points i and j and between i and k. If the slopes are equal, this implies collinearity. Slopes are compared using the cross product to avoid division and possible floating-point inaccuracies.

The dfs function, which employs memoization (as indicated by the @cache decorator), recursively explores all combinations of covering points with the minimum lines. For each unvisited point i, we attempt to draw a line to another unvisited point j and extend this line to cover additional points k if they are collinear with i and j. Whenever we add a line (whether it covers just two points or more), we increment the count of lines.

By exploring all combinations and using memoization to store results of subproblems, we ensure that the final result is the minimum number of lines needed to cover all points.

Learn more about Math, Dynamic Programming, Backtracking and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which data structure is used to implement priority queue?

Solution Approach

The solution implementation utilizes a depth-first search algorithm augmented with memoization (also known as top-down dynamic programming) to explore different combinations efficiently. Here's a breakdown of the key elements of the approach:

  • Collinearity Check (check function): The function check(i, j, k) takes three indices corresponding to the points and determines if the points i, j, and k are collinear. This is done by comparing the cross product of vectors ji and ki. The formula ((x2 - x1) * (y3 - y1)) == ((x3 - x1) * (y2 - y1)) checks whether the areas of the triangles formed by the points are the same, confirming collinearity if the area is zero (the points fall in a straight line).

  • Depth-First Search (dfs function): The dfs(state) function finds the minimum number of lines needed to cover all points, given the current state. The state variable is a bitmask representing which points have been covered so far, where the ith bit is set if the ith point is covered.

    • The base case is when state == (1 << n) - 1 which means all points are covered, thus zero lines are needed.

    • For each point i that is not covered, the algorithm attempts to draw a new line by combining it with all other points j.

    • If a line connecting points i and j is found, the function looks for any other point k that can be covered with the same line by checking for collinearity.

    • Each time a new line is added, or a point is covered, a new state nxt is created by setting the corresponding bits in state.

    • The minimum number of lines is updated by taking the minimum value between the current ans and the result of dfs(nxt) + 1 (since a new line is added).

  • Memoization: The @cache decorator is used on the dfs function to memoize the results of previous state computations. This drastically reduces repetitive calculations and improves execution speed by caching the results of subproblems.

  • Bit Manipulation: Bitwise operations on the state variable are used to efficiently manage the set of covered points, check if a point is covered (state >> i & 1), and add points to the set (nxt | 1 << i).

The main function's job is to initiate the dfs with an initial state of 0 (no points covered), and it returns the result of the dfs function as the minimum number of lines needed.

Each of these components works together to create a powerful algorithm capable of solving the problem effectively, navigating the combinatorial complexity by leveraging dynamic programming principles.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Consider a set of points points = [[1,1], [2,2], [3,3], [4,5]]. There are a total of n = 4 points.

Our goal is to find the minimum number of lines that cover all points.

We start with the initial state as 0, indicating no points are covered yet.

  1. Starting DFS: We begin with dfs(0).

  2. Trying to Cover Points: First, we try to cover point [1,1]. We look at the next point [2,2] and draw a line between them. This line has a slope that both points agree on, and they are collinear.

  3. Extending the Line: We then try to include other points on this line. Point [3,3] also lies on this line, as the slope is consistent. However, point [4,5] does not lie on the same line since it will have a different slope when paired with any of the first three points.

  4. Updating States: The state after covering points [1,1], [2,2], and [3,3] is now (1 << 0) | (1 << 1) | (1 << 2) which is 111 in binary or 7 in decimal.

  5. Covering Remaining Points: Now, dfs(7) is called to cover the remaining points. There's only [4,5] left which is not collinear with the others, and a new line must be drawn. The updated state is 1111 in binary, or 15 in decimal, which means all points are covered.

  6. Termination: The base case of dfs is reached since state == (1 << n) - 1, which is 15. So the number of lines needed to cover state 7 is 1.

  7. Memoization: The result of dfs(7) is memoized so if we ever encounter this state again, we can return the result immediately without recalculation.

  8. Repeating DFS: The process above is repeated for different combinations of starting points and lines drawn. However, in this particular example, after the first TRY, all points are covered in the most optimal way.

Finally, the minimum number of lines needed: So, for the starting state 0, dfs(0) will give us 2, which means 2 lines are needed – one line for points [1,1], [2,2], and [3,3], and another line for point [4,5].

In the actual implementation, the algorithm will explore all possible line combinations, but with memoization, redundant calculations are prevented, leading to an efficient solution.

Solution Implementation

1from functools import lru_cache
2from math import inf
3
4class Solution:
5    def minimumLines(self, stockPrices):
6        # Helper function to determine if three points are collinear
7        def are_points_collinear(first, second, third):
8            x1, y1 = stockPrices[first]
9            x2, y2 = stockPrices[second]
10            x3, y3 = stockPrices[third]
11            # Collinear if the slopes between each pair of points are equal
12            return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1)
13      
14        # Recursive function to find the minimum number of lines to connect all points
15        @lru_cache(maxsize=None)  # Cache results to avoid recomputation
16        def find_minimum_lines(state):
17            if state == (1 << num_points) - 1:  # Base case: all points are connected
18                return 0
19            answer = inf
20            for i in range(num_points):
21                # If point 'i' is not yet connected
22                if not (state >> i) & 1:
23                    for j in range(i + 1, num_points):
24                        next_state = state | (1 << i) | (1 << j)
25                        # Check if any other point 'k' is collinear with 'i' and 'j'
26                        for k in range(j + 1, num_points):
27                            if not (next_state >> k) & 1 and are_points_collinear(i, j, k):
28                                next_state |= 1 << k
29                        # Recur to the next state, adding one line for the connection made
30                        answer = min(answer, find_minimum_lines(next_state) + 1)
31                    # Special case for the last point in the list
32                    if i == num_points - 1:
33                        answer = min(answer, find_minimum_lines(state | (1 << i)) + 1)
34            return answer
35
36        num_points = len(stockPrices)
37        # Sort the stock prices based on their x-coordinate (assuming they're unsorted)
38        stockPrices.sort()
39        # Start the recursive function with the initial state of no points connected
40        return find_minimum_lines(0)
41
1class Solution {
2    private int[] dp; // memoization for the states visited
3    private int[][] points; // the array of points to draw lines through
4    private int numPoints; // total number of points
5
6    public int minimumLines(int[][] points) {
7        numPoints = points.length;
8        this.points = points;
9        dp = new int[1 << numPoints]; // initialize dp array to hold states for subsets of points
10        return dfs(0); // begin DFS with an empty state
11    }
12
13    private int dfs(int state) {
14        // If all points are included in the state, no further lines are needed
15        if (state == (1 << numPoints) - 1) {
16            return 0;
17        }
18        // If this state has already been computed, return its value
19        if (dp[state] != 0) {
20            return dp[state];
21        }
22        int minLines = Integer.MAX_VALUE; // start with the maximum value as we want to minimize
23        // Try all possible pairs of points to extend the current state
24        for (int i = 0; i < numPoints; ++i) {
25            if (((state >> i) & 1) == 0) { // if the ith point is not yet included
26                for (int j = i + 1; j < numPoints; ++j) {
27                    // State after adding the ith and jth point
28                    int nextState = state | 1 << i | 1 << j;
29                    // Extend this line to as many points as possible
30                    for (int k = j + 1; k < numPoints; ++k) {
31                        if (((state >> k) & 1) == 0 && checkCollinear(i, j, k)) {
32                            nextState |= 1 << k; // add kth point if it's collinear
33                        }
34                    }
35                    // Compute the answer for the next state plus one more line
36                    minLines = Math.min(minLines, dfs(nextState) + 1);
37                }
38                // Special case when the current point is at the end and must be connected by a unique line
39                if (i == numPoints - 1) {
40                    minLines = Math.min(minLines, dfs(state | 1 << i) + 1);
41                }
42            }
43        }
44        // Store the computed minimum lines for future reference and return it
45        return dp[state] = minLines;
46    }
47
48    // Helper method to check if three points are collinear
49    private boolean checkCollinear(int i, int j, int k) {
50        long x1 = points[i][0], y1 = points[i][1];
51        long x2 = points[j][0], y2 = points[j][1];
52        long x3 = points[k][0], y3 = points[k][1];
53        // Using cross product to check collinearity: (x2-x1)(y3-y1) = (x3-x1)(y2-y1)
54        return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);
55    }
56}
57
1#include <vector>
2#include <functional>
3#include <cstring>
4#include <algorithm>
5
6using std::vector;
7using std::function;
8using std::memset;
9using std::min;
10
11class Solution {
12public:
13    // Calculates the minimum number of lines to connect all points
14    int minimumLines(vector<vector<int>>& points) {
15        // Function to check if three points are on the same line
16        auto areCollinear = [&](int first, int second, int third) {
17            int x1 = points[first][0], y1 = points[first][1];
18            int x2 = points[second][0], y2 = points[second][1];
19            int x3 = points[third][0], y3 = points[third][1];
20            return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);
21        };
22      
23        int n = points.size();
24        int dpState[1 << n]; // dpState represents the minimum number of lines required for each state
25        memset(dpState, 0, sizeof dpState);
26      
27        // Depth-first search function to find the minimum number of lines
28        function<int(int)> dfs = [&](int state) -> int {
29            // Base case: all points are covered
30            if (state == (1 << n) - 1) return 0;
31
32            if (dpState[state]) return dpState[state]; // Return already computed result
33          
34            int ans = INT_MAX; // Initialize answer to a large value
35          
36            // Try connecting every pair of points and recursively calculate the number of lines
37            for (int i = 0; i < n; ++i) {
38                // Check if point i is not yet connected
39                if (!(state >> i & 1)) {
40                    for (int j = i + 1; j < n; ++j) {
41                        int nextState = state | 1 << i | 1 << j; // Connect points i and j
42                        // Try to add more points to the line formed by i and j
43                        for (int k = j + 1; k < n; ++k) {
44                            if (!(nextState >> k & 1) && areCollinear(i, j, k)) {
45                                nextState |= 1 << k;
46                            }
47                        }
48                        // Recurse for the next state and add a new line
49                        ans = min(ans, dfs(nextState) + 1);
50                    }
51                    // Special case for the last point when forming a line isn't possible
52                    if (i == n - 1) {
53                        ans = min(ans, dfs(state | 1 << i) + 1);
54                    }
55                }
56            }
57            return dpState[state] = ans; // Store the result in dpState
58        };
59        // Start DFS with the initial state of no points connected
60        return dfs(0);
61    }
62};
63
1// Type alias for representing points as two-dimensional arrays
2type Point = [number, number];
3
4// Checks if three points are on the same line
5const areCollinear = (first: number, second: number, third: number, points: Point[]): boolean => {
6  const [x1, y1] = points[first];
7  const [x2, y2] = points[second];
8  const [x3, y3] = points[third];
9  return (x2 - x1) * (y3 - y1) === (x3 - x1) * (y2 - y1);
10};
11
12// Initializes the variable to hold the minimum number of lines required for each state
13let dpState: number[] = [];
14
15// Depth-first search function to find the minimum number of lines
16const dfs = (state: number, points: Point[], n: number): number => {
17  // Base case: all points are covered
18  if (state === (1 << n) - 1) return 0;
19
20  // Return the already computed result
21  if (dpState[state]) return dpState[state];
22
23  let ans = Infinity; // Initialize the answer to a large value
24
25  // Try connecting every pair of points and recursively calculate the number of lines
26  for (let i = 0; i < n; ++i) {
27    // Check if point i is not yet connected
28    if (!(state & (1 << i))) {
29      for (let j = i + 1; j < n; ++j) {
30        let nextState = state | (1 << i) | (1 << j); // Connect points i and j
31      
32        // Try to add more points to the line formed by i and j
33        for (let k = j + 1; k < n; ++k) {
34          if (!(nextState & (1 << k)) && areCollinear(i, j, k, points)) {
35            nextState |= 1 << k;
36          }
37        }
38        // Recurse for the next state and add a new line
39        ans = Math.min(ans, dfs(nextState, points, n) + 1);
40      }
41      // Special case for the last point when forming a line isn't possible
42      if (i === n - 1) {
43        ans = Math.min(ans, dfs(state | (1 << i), points, n) + 1);
44      }
45    }
46  }
47  // Store the result in dpState
48  dpState[state] = ans;
49  return ans;
50};
51
52// Calculates the minimum number of lines to connect all points
53const minimumLines = (points: Point[]): number => {
54  const n = points.length;
55  dpState = new Array(1 << n); // Re-initializes the dpState array
56
57  // Start DFS with the initial state of no points connected
58  return dfs(0, points, n);
59};
60
Not Sure What to Study? Take the 2-min Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

The given code aims to find the minimum number of lines required to cover all the points provided in a list. It uses a depth-first search approach (dfs) with memoization to reduce redundant calculations.

Time Complexity:

The time complexity of this algorithm can be analyzed as follows:

  1. The dfs function is called with different states, representing subsets of points. There are 2^n possible states since each of the n points can either be included or not in a subset.

  2. Inside the dfs function, there are two nested loops:

    • The outer loop iterates over n points.
    • The inner loop iterates over n points again.
  3. Within the inner loop, for every combination of points (i, j), the code checks for any k point that can be collinear with i and j using the helper function check.

  4. The check function performs a constant-time operation to determine if three points are collinear.

Following the above points, the worst-case time complexity would be O(n^3 * 2^n) because:

  • For each state, the algorithm iterates over all pairs of points (i, j) which gives O(n^2).
  • It further checks for any k that can be on the same line, adding another factor of O(n).
  • This is done for all 2^n subsets of points (dfs calls).

Space Complexity:

The space complexity can be considered based on the following:

  1. The maximum depth of the recursive dfs is 2^n, as it represents the number of states/subsets.

  2. The memoization (@cache) stores results for each state to prevent re-computation, hence it could store up to 2^n entries.

The space complexity therefore is O(2^n) due to the memoization and the recursion stack.

In summary:

  • Time Complexity: O(n^3 * 2^n)
  • Space Complexity: O(2^n)

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫