Tackling Leetcode Problem 2209. Minimum White Tiles after Covering with Carpets

Initial thoughts

It looks like initially, me and others considered a greedy approach to optimize the placement of carpets to cover the most white tiles at each step. With counterexamples It became clear though that the approach didn't yield the optimal solution. From the solutions section it seemed was rather necessary to find the optimal solution at each step and sum those together to get the minimum possible white tiles visible at the end.

My first approach the first time I encountered this problem 6 months ago was likely manipulating arrays somehow. Trying the greedy this second time and finding a couple counter examples, I discarded it quickly.

It was kind of interesting to see this kind of problem the first time around. Labelled as 'hard' the difficulty was a bit intimidating.

If I recall correctly, it was probably the first time I saw the use of diagrams to explain the problem statement.

Past experiences

I've come across similar problems or topics related to dynamic programming before, but this is likely the first of its kind I tackled. The concept often feels confusing, especially around the pre-computation of values to be reused later. Understanding solutions is complex on its on, but devising my own can and still to this day does feel hellish.

I've seen similar problems with tags strings and prefix sum (another term for cumulative sum). The problem made me recall the latter concept, and the wikipedia article I first clarified it with.

The dynamic programming approach required here keeps a sum of the remaining visible white tiles in a two-dimensional array at each position, which is a bit reminiscent of problems with prefix sum I've encountered before.

ChatGPT interaction

With ChatGPT I usually follow a couple prompting patterns for seeking tag explanations and understanding tricky solutions on LeetCode, often times from specific recurrent LeetCode users like Lee215 whose English may be tricky to read but solutions are spot on. I find ChatGPT useful in elaborating on those solutions, explaining the logic and code involved in a structured manner, to enhance understanding

I prefer to ask ChatGPT to clarify existing human made solutions rather than asking it to provide new ones himself, as it can sometimes hallucinate or offer less optimal solutions.

Initially, I thought a greedy approach might work but soon realized it led to suboptimal solutions.

Through interactions and reviewing different solutions, I explored solutions with different approaches to dynamic programming, learning more about bottom-up and top-down strategies, and when to use dynamic programming.

I didn't get to ask all my questions to it due to time constraints. The problem is significantly more difficult to process than others I've written about and confronted before, and in such cases my method's cue to move on is placed to the test.

My experience has been that the quicker I move away from frustration, while actively seeking it through making and testing assumptions, the faster I learn.

I also wondered if the problem could be approached as a sliding window scenario, considering each carpet's starting index rather than a greedy placement. Initially, I pursued a wrong route based on this insight. This evolved through discovering a crucial example in the discussion section and self-discovery in isolation, leading me to understand that the problem had a larger search space with more possibilities for carpet placement combinations.

I also used ChatGPT to tweak around a more in-depth second solution compared to user Lee215's succinct, Pythonic solution.

Tricky Parts

As I said, it was tricky figuring out how to traverse the space of carpet placement combinations. Dynamic programming (DP) is always a bit daunting on its difficulty to grasp and for me it often is the case that it doesn't intuitively come to mind as a solution.

Although there weren't any tricky coding constraints, understanding the DP approach and the problem's optimal substructure was challenging still. The goal is to minimize something by finding minima in sub-sequences, which in general is hard to visualize.

With more learning and a closer look, I might get better at it, but I still don't feel strong on this one and for that reason haven't been able to mark it as understood on my database just yet.

Solution

class Solution:
    def minimumWhiteTiles(self, floor, k, l):

        @lru_cache(None)
        def dp(i, k):
            if i <= 0: return 0
            return min(int(floor[i - 1]) + dp(i - 1, k), dp(i - l, k - 1) if k else 1000)

        return dp(len(floor), k) 

As mentioned, the solution revolves around a DP approach to minimize the number of visible white tiles after placing a given number of carpets on a floor represented by the string floor. The core of this solution is the dp function, which is memoized using lru_cache to improve performance by storing the results of previous computations -that's what memoization means.

The dp function takes two arguments: i, the current index in the string representing the floor, and k, the number of carpets left to lay. The function is called recursively, working from right to left across the string, considering two main choices at each step: placing a carpet or not:

1. Not Placing a Carpet: If a carpet isn't placed at the current index, the function adds 1 to the count if a white tile is present (int(A[i - 1]) converts the character at the current index to an integer, adding 1 if it's a white tile), and then dp calls itself recursively with i - 1, moving one step to the left, keeping the count of carpets k left to place unchanged.

2. Placing a Carpet: If a carpet is placed, the function calls itself also with i - l, jumping by the length of a carpet (we skip l positions because a carpet is there), and k - 1, reducing the count of remaining carpets by 1. However, this choice is only considered if there are carpets left to place (k is not zero), otherwise, a large value (1000) is used to represent an undesirable choice, effectively ignoring this option, and always going for the other side of min.

The recursion continues until the left end of the string is reached (i <= 0), at which point 0 is returned, serving as the base case to terminate the recursion.

The main method initiates the dynamic programming process by calling dp with the initial index set to the length of the string floor, and the initial count of carpets k, and returns the result, representing the minimum number of visible white tiles after placing all carpets optimally.

Optimization

Just understanding the actual complexity as described by these guys was initially challenging. With dynamic programming, it seems like the states are built around the indexes or tiles and the number of carpets k. So, the states are essentially what happens at a particular index after placing a certain number of carpets.

The complexity arises as we consider all positions from 0 to n (length of floor) and all carpet counts from 0 to k, leading to n times k states.

There are weird scenarios, like stacking a bunch of carpets at index 0, which feels illogical and calls for optimization to eliminate such considerations. These states seemed to inflate the space complexity and possibly the time complexity too.

Learned

This problem dives into the core of dynamic programming and gave me an opportunity to work on its fundamental concepts. I got to grasp, perhaps to an intermediate extent, the essence of recursiveness, tabulation, and memoization, and how the same ideas can be implemented with iterative rather than recursive code, essentially tabulating states.

I got a little bit of an initial handle on optimally solving problems, understanding how tackling larger problems with optimal solutions to smaller sub-problems aligns with dynamic programming.

I was able to expose the inadequacy of a greedy approach, affirming that dynamic programming, is the suitable strategy for such problems that are optimal in structure. I think this was the most significant realization of the session.

Further

The resources I used were basically the convo with ChatGPT on this topic that I had today and yesterday. And the couple solutions (first and second)from users on LeetCode I feed as context to ChatGPT and drew understanding from.