Remove Boxes Solution in Python

Problem Description

Welcome to the world of “Remove Boxes,” where your task is to pop boxes like they’re balloons at a birthday party! Imagine you have a collection of boxes, each with a number on it, and your goal is to maximize your score by removing them strategically. The catch? You can only remove boxes that are adjacent and of the same number.

Think of it like cleaning your room: you can only throw away the boxes that are stacked together. If you manage to pop a box, you get points equal to the square of the number of boxes you just popped. So, if you pop three boxes at once, you score a whopping 9 points! But if you pop them one by one, you might end up with fewer points.

So, how do you maximize your score? That’s the million-dollar question!

Code Solution


class Solution:
    def removeBoxes(self, boxes: list[int]) -> int:
        @functools.lru_cache(None)
        def dp(i: int, j: int, k: int) -> int:
            if i > j:
                return 0

            r = j
            sameBoxes = k + 1
            while r > 0 and boxes[r - 1] == boxes[r]:
                r -= 1
                sameBoxes += 1
            res = dp(i, r - 1, 0) + sameBoxes * sameBoxes

            for p in range(i, r):
                if boxes[p] == boxes[r]:
                    res = max(res, dp(i, p, sameBoxes) + dp(p + 1, r - 1, 0))

            return res

        return dp(0, len(boxes) - 1, 0)

Approach Explanation

The solution employs a dynamic programming approach with memoization to efficiently calculate the maximum score. The dp function takes three parameters: i (the starting index), j (the ending index), and k (the count of boxes that are the same as the last box).

Base Case: If i is greater than j, it means there are no boxes left to pop, so the score is 0.
Count Same Boxes: The algorithm counts how many boxes of the same type are adjacent to the last box being considered.
Recursive Calculation: It recursively calculates the maximum score by either popping boxes in the current range or splitting the range into two parts and calculating the score for each part.

Time and Space Complexity

Time Complexity: O(n³), where n is the number of boxes. This is due to the nested loops and recursive calls.

Space Complexity: O(n²) for the memoization cache used to store results of subproblems.

Real-World Example

Imagine you’re at a party, and there are boxes of different snacks. You can only take boxes that are next to each other and of the same type. If you grab a whole stack of chocolate boxes, you score big points! But if you take them one by one, you might end up with a sad snack score. The goal is to maximize your snack score by strategically grabbing those boxes!