2209. Minimum White Tiles After Covering With Carpets

HardStringDynamic ProgrammingPrefix Sum
Leetcode Link

Problem Description

In this LeetCode problem, we have a binary string floor representing the colors of tiles on a floor, where '0' indicates a black tile and '1' indicates a white tile. We are given a certain number of black carpets (numCarpets) and the length of each carpet (carpetLen). The goal is to cover as many white tiles as possible with these carpets, minimizing the number of white tiles that remain visible. Carpets can overlap, and we need to calculate the minimum number of white tiles that will be left uncovered after optimally placing the carpets.

Intuition

To solve this problem, we need to find an optimal way to place the carpets to cover the maximum number of white tiles. Since carpets can overlap, we have to make decisions at each step regarding where to place a carpet and whether to use it at the current position or save it for later.

Given the nature of the problem, we can think of a dynamic programming approach where we keep track of the number of carpets left (j) and which position we are at (i) in the string. As we encounter a white tile (represented by '1'), we have two choices: either place a carpet here or skip this tile. If we decide to place a carpet, all tiles from the current position to the length of the carpet will be covered. If we skip, we move on to the next tile.

The solution uses a depth-first search (DFS) function with memoization (achieved through the @cache decorator) to remember the results of subproblems. The DFS function calculates the minimum number of white tiles revealed for each scenario and returns the minimum of covering the current tile or moving ahead. Thus, this approach uses a top-down dynamic programming strategy to optimize carpet placement and achieve the desired result.

The additional array s is maintained to keep track of the cumulative sum of white tiles up to any given position for quick calculation of white tiles left when we decide to skip placing a carpet. This setup aids in optimizing the process by avoiding the need to recount white tiles in subproblems repeatedly.

After computing the answer using the DFS approach, the cache_clear() method is called to clear the cache, ensuring that the cache is not filled with stale values from previous test cases.

Learn more about Dynamic Programming and Prefix Sum patterns.

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

Which of the following is a good use case for backtracking?

Solution Approach

The implementation of the solution involves dynamic programming combined with depth-first search (DFS) and memoization. Here are the steps and algorithms used in the implementation:

  1. DFS with Memoization: The main algorithm employed is a recursive DFS function dfs(i, j) that takes two parameters—i, the current tile index in the floor, and j, the number of carpets remaining. The recursion explores different scenarios of placing or not placing carpets and recalls optimal substructure results via memoization to prevent redundant calculations (@cache decorator).

  2. Base Case Handling: The base cases are when we've considered all the tiles (i.e., i >= n, where n is the length of floor), or when there are no carpets left (j == 0). The former case returns 0 since there are no more tiles to cover, and the latter returns the total number of white tiles remaining starting from index i to the end (s[-1] - s[i]).

  3. Making Decisions: When at a black tile ('0'), we can simply move to the next tile (dfs(i + 1, j)). When at a white tile ('1'), there's a choice to make: either cover it with a carpet (and evaluate dfs(i + carpetLen, j - 1), where i + carpetLen represents skipping all covered tiles and j - 1 decrements the available carpets) or leave it uncovered (and evaluate 1 + dfs(i + 1, j) where 1 represents the current white tile left uncovered). The recursive DFS function returns the minimum of these two scenarios.

  4. Cumulative Sum Array: The array s serves to pre-compute the prefix sum of white tiles at each index, where s[i + 1] = s[i] + int(floor[i] == '1'). This allows fast calculation of white tiles over a range of indices, optimizing the process when determining how many white tiles would remain if no carpet is placed starting from a particular index.

  5. Calling DFS and Clearing Cache: The solution ultimately calls dfs(0, numCarpets) to start the process from the beginning of the floor with all carpets available. Once the result is computed, dfs.cache_clear() is called to reset the memoization before handling the next test case.

The intelligent use of depth-first search with memoization to remember previous results, combined with cumulative sum logic for efficiency, brings the complexity of an otherwise exponential brute force solution down to a manageable level, enabling the solving of larger inputs effectively.

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

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose the binary string floor is "1100101", we are given numCarpets = 2, and carpetLen = 2. We aim to cover as many white tiles as possible with these carpets.

  1. Initialization: We first create a cumulative sum array s with an additional 0 at the beginning to handle zero-indexed arrays easily. For the string "1100101", s = [0, 1, 2, 2, 2, 3, 4, 5]. This array will help in quickly calculating the number of white tiles we have between any two given indices.

  2. Recursive DFS Call: We start the DFS process from index 0 with all carpets available (dfs(0, 2)).

  3. Making Decisions:

    • At index 0, we have a white tile. We have two choices:
      • Place a carpet and move two tiles ahead, dfs(2, 1).
      • Skip the tile, leaving it uncovered, 1 + dfs(1, 2).
    • Let's say we decide to place a carpet. Now at index 2, we have a choice again:
      • Place a carpet from 2 to 4 and move carpet length ahead, dfs(4, 0).
      • Skip the tile, s[-1] - s[2] + dfs(3, 1) (since j is not 0, we perform s[-1] - s[2] to count the remaining white tiles starting from index 2).

  4. Evaluating scenarios with memoization: Each of these scenarios is evaluated, and the DFS function will keep track of the scenario yielding the minimum number of white tiles left uncovered.

  5. Base Cases: Whenever i >= n (beyond last index) or j == 0, we handle the base cases as previously detailed.

After making optimal choices at each step and using memoization to avoid repeated calculations, the recursive function will yield the minimum number of white tiles that will remain uncovered. For the above example, two carpets will cover tiles from indices 0 to 1 and 2 to 3 or 4 to 5, depending on the decision made at index 2. In both cases, there will be 2 white tiles showing—the minimum for this configuration.

Upon finishing the evaluation, we call dfs.cache_clear() to prepare the memoization for the next test case if needed, without interference from the current state. Following this approach results in an efficient solution to the problem.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def minimumWhiteTiles(self, floor: str, num_carpets: int, carpet_len: int) -> int:
5        # Using LRU cache to memorize results reducing time complexity
6        @lru_cache(maxsize=None)
7        def dfs(index, remaining_carpets):
8            # If we've considered all tiles or have no remaining carpets
9            if index >= n or remaining_carpets == 0:
10                # Return the sum of white tiles starting from the current index
11                return suffix_sum[n] - suffix_sum[index]
12          
13            # If the current tile is white, we need to consider it
14            if floor[index] == '1':
15                # We have the choice to place a carpet or leave the tile exposed
16                return min(dfs(index + 1, remaining_carpets), # Leave tile exposed
17                           dfs(index + carpet_len, remaining_carpets - 1)) # Place a carpet
18            else:
19                # If the current tile is already black, just move to the next tile
20                return dfs(index + 1, remaining_carpets)
21
22        n = len(floor)
23      
24        # Precompute the prefix sum of white tiles to use later in calculation
25        suffix_sum = [0] * (n + 1)
26        for i in range(n):
27            suffix_sum[i + 1] = suffix_sum[i] + (floor[i] == '1')
28      
29        # Calculate the minimum number of white tiles using DFS starting from tile index 0 with all carpets available
30        min_white_tiles = dfs(0, num_carpets)
31      
32        # Clear the cache for the lru_cache decorator as it's a good practice to free up memory after use
33        dfs.cache_clear()
34        return min_white_tiles
35
36# Example usage (uncomment to run):
37# sol = Solution()
38# print(sol.minimumWhiteTiles("10101", 2, 2)) # Should output the minimum number of white tiles
39
1class Solution {
2    private int[][] memo; // memoization table
3    private int[] prefixSums; // prefix sums array for '1's in the floor string
4    private int floorLength; // length of the 'floor' string
5    private int carpetLength; // the length of a single carpet
6
7    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
8        floorLength = floor.length();
9        memo = new int[floorLength][numCarpets + 1];
10      
11        // Initialize the memoization table with -1 to indicate uncalculated states
12        for (int[] row : memo) {
13            Arrays.fill(row, -1);
14        }
15      
16        // Precompute the prefix sums of '1's in the floor string
17        prefixSums = new int[floorLength + 1];
18        for (int i = 0; i < floorLength; ++i) {
19            prefixSums[i + 1] = prefixSums[i] + (floor.charAt(i) == '1' ? 1 : 0);
20        }
21      
22        carpetLength = carpetLen;
23      
24        // Start the recursive depth-first search from position 0 with all carpets available
25        return dfs(0, numCarpets);
26    }
27
28    private int dfs(int position, int remainingCarpets) {
29        // If we have reached past the end of the floor, no more white tiles to cover
30        if (position >= floorLength) {
31            return 0;
32        }
33        // If we have no carpets left, return the number of white tiles until the end
34        if (remainingCarpets == 0) {
35            return prefixSums[floorLength] - prefixSums[position];
36        }
37        // If the result has been computed before, return it from the memoization table
38        if (memo[position][remainingCarpets] != -1) {
39            return memo[position][remainingCarpets];
40        }
41        // If the current floor tile is not white, go to next tile
42        if (prefixSums[position + 1] == prefixSums[position]) {
43            return dfs(position + 1, remainingCarpets);
44        }
45        // Consider two scenarios:
46        // 1. Cover the current tile with a carpet and move the position by carpetLength
47        // 2. Leave the current tile white and move to the next tile
48        int minWhiteTiles = Math.min(
49            1 + dfs(position + 1, remainingCarpets), // not using a carpet here
50            dfs(position + carpetLength, remainingCarpets - 1) // using a carpet
51        );
52        // Save the result to the memoization table
53        memo[position][remainingCarpets] = minWhiteTiles;
54        return minWhiteTiles;
55    }
56}
57
1#include <vector>
2#include <string>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
10        int n = floor.size();
11      
12        // Create a memoization table with an initial value of -1.
13        vector<vector<int>> dp(n, vector<int>(numCarpets + 1, -1));
14
15        // Create a prefix sum array 's' where s[i] indicates the number of white tiles up to index i-1.
16        vector<int> prefixSum(n + 1);
17        for (int i = 0; i < n; ++i) {
18            prefixSum[i + 1] = prefixSum[i] + (floor[i] == '1');
19        }
20
21        // Declare the dfs function to be used for the memoization.
22        function<int(int, int)> dfs;
23
24        dfs = [&](int pos, int remainingCarpets) {
25            if (pos >= n) {
26                // Base case: if we've covered the entire floor, no white tiles are left.
27                return 0;
28            }
29            if (remainingCarpets == 0) {
30                // If no carpets are left, return the count of remaining white tiles.
31                return prefixSum[n] - prefixSum[pos];
32            }
33            if (dp[pos][remainingCarpets] != -1) {
34                // Return the result from the memoization table if already computed.
35                return dp[pos][remainingCarpets];
36            }
37            if (prefixSum[pos + 1] == prefixSum[pos]) {
38                // If the current position has no white tile, move to the next position.
39                return dfs(pos + 1, remainingCarpets);
40            }
41
42            // Recurrence relation:
43            // min(putting a carpet here and moving forward by carpetLen, not putting a carpet here
44            // and considering the current white tile uncovered)
45            int ans = min(dfs(pos + carpetLen, remainingCarpets - 1), 1 + dfs(pos + 1, remainingCarpets));
46
47            // Save the result in the memoization table before returning.
48            dp[pos][remainingCarpets] = ans;
49          
50            return ans;
51        };
52
53        // Start the dfs from the first position with all carpets available.
54        return dfs(0, numCarpets);
55    }
56};
57
1// Importing functionalities from the standard library (instead of #include which is C++ syntax)
2import { memoize } from 'lodash';
3
4// Global variable declarations (every variable used matches Typescript's syntax)
5let n: number;
6let carpetLen: number;
7let prefixSum: number[];
8const dp: number[][] = [];
9
10// Utility function to compute the prefix sum array.
11// This function calculates the cumulative sum of white tiles up to each index.
12function computePrefixSum(floor: string) {
13    prefixSum = new Array(n + 1).fill(0);
14    for (let i = 0; i < n; ++i) {
15        prefixSum[i + 1] = prefixSum[i] + (floor[i] === '1' ? 1 : 0);
16    }
17}
18
19// The memoization of dfs using a higher-order function - this would be typical in Typescript to handle previous state.
20// Since there's no direct equivalent of `std::function` from C++, we use Typescript function types.
21const dfs: (pos: number, remainingCarpets: number) => number = memoize(
22    (pos: number, remainingCarpets: number): number => {
23        if (pos >= n) {
24            return 0; // Base case: if we've covered the entire floor, no white tiles are left.
25        }
26        if (remainingCarpets === 0) {
27            return prefixSum[n] - prefixSum[pos]; // No carpets left: return count of white tiles.
28        }
29        if (dp[pos][remainingCarpets] !== -1) {
30            return dp[pos][remainingCarpets]; // Return memoized result if present
31        }
32        if (prefixSum[pos + 1] === prefixSum[pos]) {
33            return dfs(pos + 1, remainingCarpets); // No white tile at current, move to next
34        }
35
36        // Decision to put or not put a carpet
37        let result = Math.min(
38            dfs(pos + carpetLen, remainingCarpets - 1), // Putting a carpet here
39            1 + dfs(pos + 1, remainingCarpets)          // Not putting carpet here
40        );
41
42        dp[pos][remainingCarpets] = result; // Update memoization table
43        return result;
44    }
45);
46
47// This function initializes the dp array and computes the minimum number of white tiles after placing the carpets.
48// This is the equivalent of the `minimumWhiteTiles` method in the provided C++ solution.
49function minimumWhiteTiles(floor: string, numCarpets: number, carpetLength: number): number {
50    n = floor.length; // Size of the floor
51    carpetLen = carpetLength; // Length of one carpet
52    dp.length = 0; // Resetting dp if already filled
53
54    // Initializing memoization table with initial value of -1
55    for (let i = 0; i < n; i++) {
56        dp.push(new Array(numCarpets + 1).fill(-1));
57    }
58
59    // Compute prefix sum only once at the beginning to use throughout
60    computePrefixSum(floor);
61
62    // Start the dfs from the first position with all carpets available
63    return dfs(0, numCarpets);
64}
65
Not Sure What to Study? Take the 2-min Quiz：

A heap is a ...?

Time and Space Complexity

Time Complexity

The overall time complexity of the given algorithm is determined by the number of states the dynamic programming needs to compute and the time it takes to compute each state. The algorithm uses a top-down dynamic programming (DFS) approach with memoization.

  • The function dfs is a recursive function with two parameters i and j, which represent the current index in the string floor and the number of carpets left to use, respectively.
  • i can have a maximum of n different states, where n is the length of the floor string.
  • j can have a maximum of numCarpets + 1 different states (ranging from 0 to numCarpets).
  • For each state, dfs makes at most two recursive calls, representing the two choices available: either place a carpet at the current position or not.

Map this into time complexity, assuming n is the length of the string floor and c is the number of carpets numCarpets:

T(n, c) = T(n - 1, c) (move to the next tile without placing a carpet) + T(n - carpetLen, c - 1) (place a carpet and skip carpetLen tiles)

Solving this, we have O(n * c * c2) time complexity, where c2 is the work done for each state. Hence, the total time complexity is O(n * c * 2).

Space Complexity

The space complexity of the algorithm includes the space required for memoization and the depth of the recursive call stack.

  • Memoization requires O(n * c) space since it stores a result for each possible state (i, j).
  • The recursion depth can go as deep as n because we might go down one level deeper for each tile.

Therefore, the overall space complexity is O(n * c) + O(n). Since O(n * c) is the dominating term, the simplified space complexity is also O(n * c).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 👨‍🏫