Skip to main content
Talentd

Minimum White Tiles After Covering With Carpets - Solution & Explanation

HardStringDynamic ProgrammingPrefix Sum20 min readAsked at: Google
Practice this problem

Problem Statement

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.
  • On the other hand, 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 <= 1000
  • floor[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.

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n * numCarpets), where n is the length of the floor string.
Space Complexity: O(n * numCarpets), used by the dp array.

Try this approach in the editor →

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.

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.

Code

C++

C++

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

Approach 4: 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, return 0;
  • 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 array s to 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n * numCarpets), where n is the length of the floor string.
Space Complexity: O(n * numCarpets), used by the dp array.

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.
Space Complexity: O(n) for the prefix sum array.

Greedy with Precomputation

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.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(n * k)O(n * k)General case where optimal placement decisions must consider overlapping carpet intervals
Sliding Window with Prefix SumO(n * k)O(n)When fast segment queries are needed to evaluate many carpet placements efficiently
Greedy with PrecomputationO(n * k)O(n)Useful for simpler reasoning when prioritizing segments that cover the most white tiles

Video Solution

2209. Minimum White Tiles After Covering With Carpets || Biweekly Contest 74 || Leetcode 2209 • Bro Coders • 2,420 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Minimum White Tiles After Covering With Carpets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Edit Distance