Minimum White Tiles After Covering With Carpets solution and explanation
Google
4 more videos on this problem
2209. Minimum White Tiles After Covering With Carpets || Biweekly Contest 74 || Leetcode 2209Bro Coders · 17:07 · 2K views
2209. Minimum White Tiles After Covering With Carpets (Leetcode Hard)Programming Live with Larry · 13:10 · 1K views
Leetcode BiWeekly 74 | 2209. Minimum White Tiles After Covering With CarpetscodingMohan · 10:51 · 1K views
【每日一题】LeetCode 2209. Minimum White Tiles After Covering With CarpetsHuifeng Guan · 25:01 · 463 views
2209. Minimum White Tiles After Covering With Carpets (Hard) || LeetCode The Hard WayLeetCode The Hard Way · 6:15 · 118 views
The problem
You are given a 0-indexed binary string floor, which represents the colors of tiles on a floor:
floor[i] = '0'denotes that theithtile of the floor is colored black.- On the other hand,
floor[i] = '1'denotes that theithtile 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 <= 1000
Approach overview
Problem 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.
Approach 1: Dynamic Programming Approach
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.
def min_white_tiles(floor, numCarpets, carpetLen):
n = len(floor)
prefix_white = [0] * (n + 1)
for i in range(n):
prefix_white[i + 1] = prefix_white[i] + (1 if floor[i] == '1' else 0)
dp = [[0] + [float('inf')] * numCarpets for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(numCarpets + 1):
dp[i][j] = dp[i - 1][j] + (1 if floor[i - 1] == '1' else 0)
if j > 0 and i >= carpetLen:
dp[i][j] = min(dp[i][j], dp[i - carpetLen][j - 1])
return dp[n][numCarpets]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.
Approach 2: Sliding Window with Prefix Sum Approach
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.
#include <vector>
#include <string>
#include <algorithm>
int minWhiteTiles(std::string floor, int numCarpets, int carpetLen) {
int n = floor.size(), maxCover = 0;
std::vector<int> preWhite(n + 1, 0);
for (int i = 0; i < n; ++i)
preWhite[i + 1] = preWhite[i] + (floor[i] == '1');
for (int i = 0; i <= n - carpetLen; ++i) {
int covered = preWhite[i + carpetLen] - preWhite[i];
maxCover = std::max(maxCover, covered);
}
int totalWhite = preWhite[n];
int visibleWhite = totalWhite - maxCover;
return visibleWhite <= 0 ? 0 : visibleWhite;
}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.
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.
Approach 3: Dynamic Programming Approach
The key idea is to use dynamic programming to explore the minimum number of white tiles left uncovered with a certain number of carpets. We define a DP table where dp[i][j] represents the minimum white tiles visible after covering up to the ith tile using j carpets.
Transitions depend on two choices: not using a carpet on the i tile or using it. If a carpet is used, it potentially covers a segment ending at the ith tile extending backwards up to carpetLen tiles.
class Solution {
public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
int n = floor.length();
int[][] dp = new int[n+1][numCarpets+1];
for (int i = 1; i <= n; ++i)
dp[i][0] = dp[i-1][0] + (floor.charAt(i-1) == '1' ? 1 : 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= numCarpets; ++j) {
dp[i][j] = dp[i-1][j] + (floor.charAt(i-1) == '1' ? 1 : 0);
if (i >= carpetLen)
dp[i][j] = Math.min(dp[i][j], dp[i-carpetLen][j-1]);
else
dp[i][j] = Math.min(dp[i][j], 0);
}
}
return dp[n][numCarpets];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minimumWhiteTiles("11111", 2, 3)); // Output: 0
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
int n = floor.length();
vector<vector<int>> dp(n+1, vector<int>(numCarpets+1, 0));
for (int i = 1; i <= n; ++i)
dp[i][0] = dp[i-1][0] + (floor[i-1] == '1');
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= numCarpets; ++j) {
dp[i][j] = dp[i-1][j] + (floor[i-1] == '1');
if(i >= carpetLen)
dp[i][j] = min(dp[i][j], dp[i-carpetLen][j-1]);
else
dp[i][j] = min(dp[i][j], 0);
}
}
return dp[n][numCarpets];
}
int main() {
string floor = "10110101";
int numCarpets = 2;
int carpetLen = 2;
cout << minimumWhiteTiles(floor, numCarpets, carpetLen) << endl;
return 0;
}function minimumWhiteTiles(floor, numCarpets, carpetLen) {
const n = floor.length;
const dp = Array.from({length: n + 1}, () => Array(numCarpets + 1).fill(Infinity));
dp[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j <= numCarpets; ++j) {
dp[i][j] = (floor[i - 1] === '1' ? dp[i - 1][j] + 1 : dp[i - 1][j]);
if (j > 0 && i >= carpetLen)
dp[i][j] = Math.min(dp[i][j], dp[i - carpetLen][j - 1]);
}
}
return Math.min(...dp[n]);
}
console.log(minimumWhiteTiles('10110101', 2, 2)); // Output: 2#include <stdio.h>
#include <string.h>
#include <limits.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
int minimumWhiteTiles(char *floor, int numCarpets, int carpetLen) {
int n = strlen(floor);
int dp[n+1][numCarpets+1];
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= numCarpets; j++) {
dp[i][j] = INT_MAX;
}
}
dp[0][0] = 0; // no tiles, no carpets
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= numCarpets; ++j) {
if (floor[i-1] == '1') // if white tile
dp[i][j] = dp[i-1][j] + 1;
else
dp[i][j] = dp[i-1][j];
// Try laying a carpet
if (j > 0 && i >= carpetLen)
dp[i][j] = MIN(dp[i][j], dp[i-carpetLen][j-1]);
}
}
// Minimum white tiles visible with all tiles and numCarpets
int result = INT_MAX;
for (int j = 0; j <= numCarpets; ++j) {
result = MIN(result, dp[n][j]);
}
return result;
}
int main() {
char floor[] = "11111";
int numCarpets = 2;
int carpetLen = 3;
printf("%d\n", minimumWhiteTiles(floor, numCarpets, carpetLen));
return 0;
}using System;
public class Solution {
public int MinimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
int n = floor.Length;
int[,] dp = new int[n + 1, numCarpets + 1];
for (int i = 1; i <= n; ++i) {
dp[i, 0] = dp[i - 1, 0] + (floor[i - 1] == '1' ? 1 : 0);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= numCarpets; ++j) {
dp[i, j] = dp[i - 1, j] + (floor[i - 1] == '1' ? 1 : 0);
if (i >= carpetLen)
dp[i, j] = Math.Min(dp[i, j], dp[i - carpetLen, j - 1]);
else
dp[i, j] = Math.Min(dp[i, j], 0);
}
}
return dp[n, numCarpets];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinimumWhiteTiles("11111", 2, 3)); // Output: 0
}
}This Java solution utilizes a DP table initialized and filled based on whether the current tile is white or not. It decides to cover with carpets or leave a section uncovered, to maintain minimal visibility of white tiles.
Time Complexity: O(n * numCarpets)
Space Complexity: O(n * numCarpets)
Approach 4: Greedy with Precomputation
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.
def minimumWhiteTiles(floor: str, numCarpets: int, carpetLen: int) -> int:
n = len(floor)
prefix_sum = [0] * (n+1)
for i in range(1, n+1):
prefix_sum[i] = prefix_sum[i-1] + (floor[i-1] == '1')
covered = [0] * n
for _ in range(numCarpets):
max_cover = 0
position = -1
for i in range(n - carpetLen + 1):
current_cover = prefix_sum[i + carpetLen] - prefix_sum[i] - sum(covered[i:i + carpetLen])
if current_cover > max_cover:
max_cover = current_cover
position = i
if max_cover == 0:
break
for i in range(position, position + carpetLen):
covered[i] += 1
return sum((floor[i] == '1' and covered[i] == 0) for i in range(n))
print(minimumWhiteTiles("10110101", 2, 2)) # Output: 2This 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.
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.
Approach 5: Memoization Search
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:
- If
i \ge n, it means all tiles have been covered, return0; - If
floor[i] = 0, then we do not need to use a carpet, just skip it, i.e.,dfs(i, j) = dfs(i + 1, j); - If
j = 0, then we can directly use the prefix sum arraysto calculate the number of remaining uncovered white tiles, i.e.,dfs(i, j) = s[n] - s[i]; - If
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.
function minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
const n = floor.length;
const f: number[][] = Array.from({ length: n }, () => Array(numCarpets + 1).fill(-1));
const s: number[] = Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + (floor[i] === '1' ? 1 : 0);
}
const dfs = (i: number, j: number): number => {
if (i >= n) {
return 0;
}
if (j === 0) {
return s[n] - s[i];
}
if (f[i][j] !== -1) {
return f[i][j];
}
if (s[i + 1] === s[i]) {
return dfs(i + 1, j);
}
const ans = Math.min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1));
f[i][j] = ans;
return ans;
};
return dfs(0, numCarpets);
}func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
n := len(floor)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, numCarpets+1)
for j := range f[i] {
f[i][j] = -1
}
}
s := make([]int, n+1)
for i, c := range floor {
s[i+1] = s[i] + int(c-'0')
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= n {
return 0
}
if j == 0 {
return s[n] - s[i]
}
if f[i][j] != -1 {
return f[i][j]
}
if s[i+1] == s[i] {
return dfs(i+1, j)
}
ans := min(1+dfs(i+1, j), dfs(i+carpetLen, j-1))
f[i][j] = ans
return ans
}
return dfs(0, numCarpets)
}impl Solution {
pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
let n = floor.len();
let a: Vec<u8> = floor.bytes().collect();
let m = num_carpets as usize;
let k = carpet_len as usize;
let mut s = vec![0i32; n + 1];
for i in 0..n {
s[i + 1] = s[i] + if a[i] == b'1' { 1 } else { 0 };
}
let mut f = vec![vec![-1; m + 1]; n];
fn dfs(
i: usize,
j: usize,
n: usize,
k: usize,
s: &Vec<i32>,
f: &mut Vec<Vec<i32>>,
a: &Vec<u8>,
) -> i32 {
if i >= n {
return 0;
}
if j == 0 {
return s[n] - s[i];
}
if f[i][j] != -1 {
return f[i][j];
}
if s[i + 1] == s[i] {
let v = dfs(i + 1, j, n, k, s, f, a);
f[i][j] = v;
return v;
}
let t1 = 1 + dfs(i + 1, j, n, k, s, f, a);
let ni = i + k;
let t2 = dfs(ni, j - 1, n, k, s, f, a);
let t = t1.min(t2);
f[i][j] = t;
t
}
dfs(0, m, n, k, &s, &mut f, &a)
}
}Complexity comparison
| 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. |
| Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Greedy with Precomputation | Time Complexity: Space Complexity: |
| Memoization Search | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum White Tiles After Covering With Carpets easy or hard?
Minimum White Tiles After Covering With Carpets is classified as a Hard problem. The difficulty comes from modeling overlapping carpet placements and choosing the optimal placement strategy using dynamic programming.
Minimum White Tiles After Covering With Carpets Python/Java solution
Most implementations use a DP table or memoized recursion. Python solutions typically use recursion with caching or a 2D DP list, while Java implementations often use iterative DP arrays. Both achieve O(n * k) time complexity.
How to solve Minimum White Tiles After Covering With Carpets in O(n)?
Pure O(n) is generally not achievable because the number of carpets introduces another dimension of decisions. However, prefix sums allow constant-time range queries, and the dynamic programming transitions still run in O(n * k). This is considered optimal for the problem constraints.
What is the best approach for Minimum White Tiles After Covering With Carpets?
Dynamic Programming is the most reliable approach. It tracks the minimum uncovered white tiles for each position and number of carpets used. By deciding whether to place a carpet or leave a tile uncovered, the DP guarantees the optimal arrangement with O(n * k) time complexity.
Is Minimum White Tiles After Covering With Carpets asked at Google/Amazon/Meta?
Problems involving interval coverage, dynamic programming decisions, and prefix sums frequently appear in interviews at companies like Google, Amazon, and Meta. This problem reflects the same pattern of optimizing coverage over a sequence with limited resources.
What data structure is used in Minimum White Tiles After Covering With Carpets?
The main technique uses dynamic programming arrays to track states and prefix sum arrays to compute the number of white tiles in any interval quickly. The input itself is processed as a string representing the floor.
What is the time complexity of Minimum White Tiles After Covering With Carpets?
The optimal dynamic programming solution runs in O(n * k) time where n is the floor length and k is the number of carpets. Each state represents a prefix of the floor and the number of carpets used. Space complexity is also O(n * k) unless optimized.