Minimum White Tiles After Covering With Carpets LeetCode solution in Python

1
class Solution:
2
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
3
        n = len(floor)
4
        # Using memo table to store predefined computations
5
        memo = [[-1 for x in range(numCarpets + 1)] for x in range(len(floor) + 1)]
6

7
        def solve(N, numCarpets):
8
            # Base Case
9
            if N >= n:
10
                return 0
11
                # If calculated previously use that solution
12
            if memo[N][numCarpets] != -1:
13
                return memo[N][numCarpets]
14

15
            used = 0  # If you use the carpet
16
            notused = 0  # If you donot use the carpet
17

18
            if floor[N] == "1":  # We might use the carpet in this part
19
                if numCarpets > 0:  # Whether we even have some carpets or not
20
                    """
21
                    Optimization Part
22
                    We are finding the number of ones present in this part of the floor.
23
                    prefix[lastInd] - Number of ones till lastInd
24
                    prefix[N] - Number of ones till Nth Index.
25

26
                    Their difference gives us how many ones present between the two.
27
                    """
28
                    lastInd = min(N + carpetLen, len(floor))
29
                    ans = prefix[lastInd] - prefix[N]
30

31
                    """
32
                    Find the max if we use or donot use carpet at this index
33
                    If we do we add  --- ans and decrement remaining carpets
34
                    else we donot
35
                    """
36
                    used = max(
37
                        solve(N + carpetLen, numCarpets - 1) + ans,
38
                        solve(N + 1, numCarpets),
39
                    )
40

41
                else:
42
                    used = 0
43

44
            else:
45
                # If we donot use the carpet although I feel this might be redundant code
46
                notused = solve(N + 1, numCarpets)
47

48
                # Using max function to find the number of white tiles removed
49
            memo[N][numCarpets] = max(used, notused)
50
            return memo[N][numCarpets]
51

52
            # Total White tiles
53

54
        ones = 0
55
        for x in floor:
56
            if x == "1":
57
                ones += 1
58

59
                # Using Prefix array to store number of ones till i th index
60
        prefix = [0] * (n + 1)
61
        for i in range(1, n + 1):
62
            if floor[i - 1] == "1":
63
                prefix[i] = prefix[i - 1] + 1
64
            else:
65
                prefix[i] = prefix[i - 1]
66

67
        removed = solve(0, numCarpets)
68

69
        return ones - removed