2209. Minimum White Tiles After Covering With Carpets LeetCode Solution

In this guide, you will get 2209. Minimum White Tiles After Covering With Carpets LeetCode Solution with the best time and space complexity. The solution to Minimum White Tiles After Covering With Carpets problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum White Tiles After Covering With Carpets solution in C++
4. Minimum White Tiles After Covering With Carpets solution in Java
5. Minimum White Tiles After Covering With Carpets solution in Python
6. Additional Resources

Problem Statement of Minimum White Tiles After Covering With Carpets

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

Complexity Analysis

• Time Complexity: O(n \cdot \texttt{numCarpets})
• Space Complexity: O(n \cdot \texttt{numCarpets})

2209. Minimum White Tiles After Covering With Carpets LeetCode Solution in C++

class Solution {
 public:
  int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
    vector<vector<int>> mem(floor.length() + 1,
                            vector<int>(numCarpets + 1, kMax));
    return minimumWhiteTiles(floor, 0, numCarpets, carpetLen, mem);
  }

 private:
  static constexpr int kMax = 1000;

  // Returns the minimum number of visible white tiles of floor[i..n) after
  // covering at most j carpets.
  int minimumWhiteTiles(const string& floor, int i, int j, int carpetLen,
                        vector<vector<int>>& mem) {
    if (j < 0)
      return kMax;
    if (i >= floor.length())
      return 0;
    if (mem[i][j] != kMax)
      return mem[i][j];
    return mem[i][j] = min(
               minimumWhiteTiles(floor, i + carpetLen, j - 1, carpetLen, mem),
               minimumWhiteTiles(floor, i + 1, j, carpetLen, mem) + floor[i] -
                   '0');
  }
};
/* code provided by PROGIEZ */

2209. Minimum White Tiles After Covering With Carpets LeetCode Solution in Java

class Solution {
  public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
    int[][] mem = new int[floor.length() + 1][numCarpets + 1];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, kMax));
    return minimumWhiteTiles(floor, 0, numCarpets, carpetLen, mem);
  }

  private static final int kMax = 1000;

  // Returns the minimum number of visible white tiles of floor[i..n) after
  // covering at most j carpets.
  int minimumWhiteTiles(final String floor, int i, int j, int carpetLen, int[][] mem) {
    if (j < 0)
      return kMax;
    if (i >= floor.length())
      return 0;
    if (mem[i][j] != kMax)
      return mem[i][j];
    return mem[i][j] =
               Math.min(minimumWhiteTiles(floor, i + carpetLen, j - 1, carpetLen, mem),
                        minimumWhiteTiles(floor, i + 1, j, carpetLen, mem) + floor.charAt(i) - '0');
  }
}
// code provided by PROGIEZ

2209. Minimum White Tiles After Covering With Carpets LeetCode Solution in Python

class Solution:
  def minimumWhiteTiles(
      self,
      floor: str,
      numCarpets: int,
      carpetLen: int,
  ) -> int:
    kMax = 1000

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """
      Returns the minimum number of visible white tiles of floor[i..n) after
      covering at most j carpets.
      """
      if j < 0:
        return kMax
      if i >= len(floor):
        return 0
      return min(dp(i + carpetLen, j - 1),
                 dp(i + 1, j) + int(floor[i]))

    return dp(0, numCarpets)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.