Scale Engineer

Minimum White Tiles After Covering With Carpets

Hard
#2012Time: O(2^n) without memoization. The number of states can be large, and each state branches into two, leading to an exponential number of calls.Space: O(n) for the recursion stack depth in the naive version. O(n * numCarpets) if memoization is added.
Patterns
Dynamic ProgrammingPrefix Sum
Data structures
String

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, brute-force recursion to explore all possible ways of placing the carpets. For each tile, we make a decision: either we place a carpet starting at this tile (if we have any left), or we don't. This creates a decision tree that explores all combinations. While simple to understand, its exponential nature makes it impractical for all but the smallest inputs.

Algorithm

  • Define a recursive function, say solve(index, carpetsLeft), that returns the minimum number of visible white tiles from index to the end of the floor, given carpetsLeft carpets.
  • Base Cases:
    • If index is beyond the floor's end (index >= floor.length), no more tiles are left, so return 0.
    • If carpetsLeft is 0, no more carpets can be used. Return the total number of white tiles from index to the end. This can be pre-calculated using a suffix sum array for efficiency.
  • Recursive Step: At index, we have two choices:
    1. Skip: Don't place a carpet starting at index. The cost is 1 if floor[index] is white, plus the result of the recursive call for the next tile: (floor[index] == '1' ? 1 : 0) + solve(index + 1, carpetsLeft).
    2. Cover: Place a carpet starting at index. This covers tiles up to index + carpetLen - 1. The cost is the result of the recursive call for the state after the carpet ends: solve(index + carpetLen, carpetsLeft - 1).
  • The function returns the minimum of the results from these two choices.

Walkthrough

The core idea is to define a function that solves the problem for a suffix of the floor. Let's define solve(index, carpetsLeft) as the minimum white tiles visible from index onwards, with carpetsLeft available.

At each index, we face a choice:

  1. Don't place a carpet here: We move to the next tile index + 1, and if the current tile index is white, it adds to our count of visible white tiles.
  2. Place a carpet here: We use one carpet, which covers the segment [index, index + carpetLen - 1]. We then recursively solve for the subproblem starting at index + carpetLen with one less carpet.

The function returns the minimum of these two outcomes. The recursion stops when we run out of tiles or carpets.

class Solution {    private String floor;    private int n;    private int carpetLen;    private int[] suffixWhite;    private int[][] memo;     public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {        this.floor = floor;        this.n = floor.length();        this.carpetLen = carpetLen;                // Using memoization to show the transition to DP, but a pure recursive solution would omit this.        // A naive solution without memoization would be too slow.        this.memo = new int[n + 1][numCarpets + 1];        for (int[] row : memo) {            java.util.Arrays.fill(row, -1);        }         // Precompute suffix sums of white tiles for the base case        this.suffixWhite = new int[n + 1];        for (int i = n - 1; i >= 0; i--) {            suffixWhite[i] = suffixWhite[i + 1] + (floor.charAt(i) - '0');        }         return solve(0, numCarpets);    }     // This is the recursive helper. Without memoization, it's a naive approach.    private int solve(int i, int k) {        // Base cases        if (i >= n) {            return 0;        }        if (k == 0) {            return suffixWhite[i];        }        if (memo[i][k] != -1) {            return memo[i][k];        }         // Option 1: Skip tile i        int skip = (floor.charAt(i) - '0') + solve(i + 1, k);         // Option 2: Cover starting at tile i        int cover = solve(i + carpetLen, k - 1);         return memo[i][k] = Math.min(skip, cover);    }}

Complexity

Time

O(2^n) without memoization. The number of states can be large, and each state branches into two, leading to an exponential number of calls.

Space

O(n) for the recursion stack depth in the naive version. O(n * numCarpets) if memoization is added.

Trade-offs

Pros

  • Simple to conceptualize and follows the problem's decision-making process directly.

Cons

  • Extremely inefficient due to a massive number of redundant computations for the same subproblems.

  • Will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution {private  int[][] f;private  int[] s;private  int n;private  int k;public  int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {    n = floor.length();    f = new int[n][numCarpets + 1];    for (var e : f) {      Arrays.fill(e, -1);    }    s = new int[n + 1];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + (floor.charAt(i) == '1' ? 1 : 0);    }    k = carpetLen;    return dfs(0, numCarpets);  }private  int dfs(int i, int j) {    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);    }    int ans = Math.min(1 + dfs(i + 1, j), dfs(i + k, j - 1));    f[i][j] = ans;    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem