You are given a 0-indexed binary string floor, which represents the colors of tiles on a floor:
floor[i] = '0' denotes that the ith tile of the floor is colored black.floor[i] = '1' denotes that the ith tile of the floor is colored white.You are also given numCarpets and carpetLen. You have numCarpets black carpets, each of length carpetLen tiles. Cover the tiles with the given carpets such that the number of white tiles still visible is minimum. Carpets may overlap one another.
Return the minimum number of white tiles still visible.
Example 1:
Input: floor = "10110101", numCarpets = 2, carpetLen = 2 Output: 2 Explanation: The figure above shows one way of covering the tiles with the carpets such that only 2 white tiles are visible. No other way of covering the tiles with the carpets can leave less than 2 white tiles visible.
Example 2:
Input: floor = "11111", numCarpets = 2, carpetLen = 3 Output: 0 Explanation: The figure above shows one way of covering the tiles with the carpets such that no white tiles are visible. Note that the carpets are able to overlap one another.
Constraints:
1 <= carpetLen <= floor.length <= 1000floor[i] is either '0' or '1'.1 <= numCarpets <= 1000Problem Overview: You get a binary string representing a floor where '1' is a white tile and '0' is a black tile. You can place a limited number of carpets, each covering a fixed number of consecutive tiles. The goal is to place these carpets so the number of uncovered white tiles is minimized.
Approach 1: Dynamic Programming (O(n * k) time, O(n * k) space)
This approach models the problem using Dynamic Programming. Let dp[i][j] represent the minimum uncovered white tiles considering the first i tiles with j carpets available. At each tile you either leave it uncovered (add 1 if it's white) or place a carpet ending at that tile and skip the previous carpetLen tiles. The key insight is treating carpet placement as a jump in the DP state. This method guarantees the optimal result and handles overlapping decisions cleanly.
Approach 2: Sliding Window with Prefix Sum (O(n * k) time, O(n) space)
This version uses a prefix sum array to quickly count how many white tiles exist in any segment of length carpetLen. A sliding window evaluates potential carpet placements and determines how many white tiles each placement would cover. Combined with a DP or iterative optimization over carpets used, you repeatedly choose segments that maximize white tiles covered. Prefix sums make each segment query constant time, which keeps the solution efficient even when scanning many possible placements.
Approach 3: Greedy with Precomputation (O(n * k) time, O(n) space)
This strategy precomputes how many white tiles each possible carpet placement can cover. Using this information, you attempt to greedily prioritize segments that remove the most white tiles. Precomputation avoids recalculating counts for every candidate interval. While greedy alone can fail in some overlapping scenarios, combining it with tracking remaining uncovered segments makes it practical for many inputs and simpler to reason about than full DP.
Recommended for interviews: The dynamic programming approach is the expected solution. It clearly models the decision of placing or skipping a carpet and guarantees optimal results. Showing the brute reasoning first and then building the DP transition demonstrates strong problem‑solving skills and familiarity with interval-style DP problems.
This approach involves using dynamic programming to solve the problem by defining a dp array. The value of dp[i] represents the minimum number of white tiles visible when considering the first i tiles and utilizing a certain number of carpets.
To compute dp[i], you iterate over each possible position of the last carpet and calculate the number of visible white tiles, updating the dp array to store the minimum value found.
The Python solution defines a function min_white_tiles which uses dynamic programming. The prefix_white array helps compute the number of white tiles efficiently, while the dp 2D array stores the minimum number of visible white tiles for each scenario. The solution updates the dp array based on whether the current position is covered by a new carpet or not.
Time Complexity: O(n * numCarpets), where n is the length of the floor string.
Space Complexity: O(n * numCarpets), used by the dp array.
A different approach uses sliding windows combined with a prefix sum to determine the maximum number of white tiles that can be covered with a rug. Calculate the number of visible white tiles by subtracting the maximum covered tiles from the total number of white tiles.
Move the window and keep track of maximum white tiles covered within the carpet length and the number of carpets available.
This C++ solution takes advantage of prefix sums to quickly calculate the number of white tiles in any window of size carpetLen. It slides a window across the string to determine the configuration that covers the maximum number of white tiles, then subtracts this from the total number of white tiles.
C++
Time Complexity: O(n), where n is the length of the floor string due to the prefix sum and single pass window technique.
Space Complexity: O(n) for the prefix sum array.
Instead of using dynamic programming, a greedy approach can be used for certain cases, leveraging precomputation of white tiles in segments. Sum the number of white tiles visible across overlapping segments, and cover the ones with the highest values first.
This solution uses a greedy strategy to iteratively select and cover the segment with the most uncovered white tiles using the prefix sum array for quick counting, maintaining an auxiliary array to store quantities of carpets covering each tile to avoid double counting.
Python
Time Complexity: O(n * numCarpets) since we try to cover each high white count segment per carpet.
Space Complexity: O(n) due to the prefix sum and covered arrays.
We design a function dfs(i, j) to represent the minimum number of white tiles that are not covered starting from index i using j carpets. The answer is dfs(0, numCarpets).
For index i, we discuss the following cases:
i \ge n, it means all tiles have been covered, return 0;floor[i] = 0, then we do not need to use a carpet, just skip it, i.e., dfs(i, j) = dfs(i + 1, j);j = 0, then we can directly use the prefix sum array s to calculate the number of remaining uncovered white tiles, i.e., dfs(i, j) = s[n] - s[i];floor[i] = 1, then we can choose to use a carpet or not, and take the minimum of the two, i.e., dfs(i, j) = min(dfs(i + 1, j), dfs(i + carpetLen, j - 1)).We use memoization search to solve this problem.
The time complexity is O(n times m), and the space complexity is O(n times m). Here, n and m are the length of the string floor and the value of numCarpets, respectively.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * numCarpets), where n is the length of the floor string. |
| Sliding Window with Prefix Sum Approach | Time Complexity: O(n), where n is the length of the floor string due to the prefix sum and single pass window technique. |
| Greedy with Precomputation | Time Complexity: Space Complexity: |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n * k) | O(n * k) | General case where optimal placement decisions must consider overlapping carpet intervals |
| Sliding Window with Prefix Sum | O(n * k) | O(n) | When fast segment queries are needed to evaluate many carpet placements efficiently |
| Greedy with Precomputation | O(n * k) | O(n) | Useful for simpler reasoning when prioritizing segments that cover the most white tiles |
2209. Minimum White Tiles After Covering With Carpets || Biweekly Contest 74 || Leetcode 2209 • Bro Coders • 2,394 views views
Watch 4 more video solutions →Practice Minimum White Tiles After Covering With Carpets with our built-in code editor and test cases.
Practice on FleetCode