Facebook Pixel

546. Remove Boxes

Problem Description

You have a row of boxes, where each box has a color represented by a positive number. Your goal is to remove all boxes and maximize your total score.

The game works as follows:

  • In each round, you can select a group of consecutive boxes that all have the same color
  • When you remove k consecutive boxes of the same color, you earn k * k points
  • After removing boxes, the remaining boxes shift together (maintaining their order)
  • You continue removing boxes until none are left

For example, if you have boxes [1, 3, 2, 2, 2, 3, 4, 3, 1]:

  • You could remove the three consecutive 2's in the middle to get 3 * 3 = 9 points
  • Or you might remove boxes strategically in a different order to get a higher total score

The challenge is to find the optimal sequence of removals that maximizes your total points. Since removing boxes causes the remaining boxes to come together, you might want to remove certain boxes first to create larger groups of the same color later.

Your task is to determine the maximum possible points you can achieve by removing all the boxes.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that when we remove boxes, we might want to delay removing certain boxes to combine them with others of the same color later. This creates a complex decision tree where the order of removal significantly impacts the final score.

Consider a simple example: [1, 2, 1]. If we remove the middle 2 first, we get 1 * 1 = 1 point, then the two 1s come together and we can remove them for 2 * 2 = 4 points, totaling 5 points. But if we removed each box individually, we'd only get 1 + 1 + 1 = 3 points.

This suggests we need dynamic programming with memoization. But what state should we track? The naive approach of tracking which boxes have been removed would be too complex.

The clever observation is that we can define our subproblem as: "What's the maximum score for removing boxes from index i to j, where we already have k boxes of the same color as boxes[j] that will be combined with boxes[j] when it's removed?"

Why include this extra parameter k? Because when we remove some boxes in the middle, boxes on the sides come together. If those side boxes have the same color, they form a larger group that yields more points when removed together.

For the recursive case, we have two main strategies:

  1. Remove boxes[j] along with the k boxes of the same color, getting (k + 1) * (k + 1) points
  2. Look for another box with the same color as boxes[j] somewhere in the range [i, j-1], remove the boxes between them first, then combine them for a potentially higher score

The second strategy is powerful because it allows us to "save" boxes of the same color to remove them together later, potentially earning more points than removing them separately.

Learn more about Memoization and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with memoization to solve this problem. Let's break down the implementation:

State Definition:

  • dfs(i, j, k) returns the maximum points we can get from removing boxes in the range [i, j], where we have k additional boxes of the same color as boxes[j] that will be combined with it.

Base Case:

  • If i > j, there are no boxes to remove, so return 0.

Optimization Step: Before processing, we consolidate consecutive boxes of the same color at the end:

while i < j and boxes[j] == boxes[j - 1]:
    j, k = j - 1, k + 1

This merges adjacent boxes of the same color as boxes[j] into our k counter, reducing redundant calculations.

Recursive Cases:

  1. Direct Removal Strategy:

    ans = dfs(i, j - 1, 0) + (k + 1) * (k + 1)

    Remove boxes[j] along with the k boxes of the same color. This gives us (k + 1) * (k + 1) points, plus whatever we get from removing the remaining boxes [i, j-1].

  2. Merge Strategy:

    for h in range(i, j):
        if boxes[h] == boxes[j]:
            ans = max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1))

    For each box at position h that has the same color as boxes[j]:

    • First remove all boxes between h and j (exclusive): dfs(h + 1, j - 1, 0)
    • Then remove boxes from i to h, where boxes[h] now has k + 1 additional boxes (the original k plus boxes[j]): dfs(i, h, k + 1)

Memoization: The @cache decorator automatically memoizes the results, preventing redundant calculations for the same (i, j, k) state.

Time Complexity: O(n^4) where n is the number of boxes. We have O(n^3) possible states and each state takes O(n) time to compute.

Space Complexity: O(n^3) for the memoization cache.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with boxes [2, 1, 2, 1] to illustrate the solution approach.

Initial Call: dfs(0, 3, 0) - process boxes from index 0 to 3 with 0 additional boxes.

Step 1: Processing dfs(0, 3, 0)

  • Current range: [2, 1, 2, 1], boxes[3] = 1, k = 0
  • No consecutive same-color boxes at the end, so no optimization step needed

Option 1 - Direct Removal:

  • Remove boxes[3] (the 1 at index 3) immediately
  • Score: dfs(0, 2, 0) + (0 + 1)² = dfs(0, 2, 0) + 1

Option 2 - Merge Strategy:

  • Look for boxes with same color as boxes[3] (which is 1)
  • Found boxes[1] = 1
  • Remove boxes between index 1 and 3 first: dfs(2, 2, 0)
    • This removes the 2 at index 2, giving us 1 point
  • Then handle dfs(0, 1, 1) where we now have 1 additional 1 to combine
    • This processes [2, 1] where the 1 at index 1 will be combined with the saved 1
    • We can remove the 2 first: dfs(0, 0, 0) = 1 point
    • Then remove both 1s together: (1 + 1)² = 4 points
  • Total for this path: 1 + 1 + 4 = 6 points

Continuing the Direct Removal path from Step 1:

  • dfs(0, 2, 0) processes [2, 1, 2]
  • Direct removal: Remove the 2 at index 2 for 1 point, then solve dfs(0, 1, 0)
  • Merge strategy: boxes[0] = 2 matches boxes[2]
    • Remove middle box: dfs(1, 1, 0) = 1 point (remove the 1)
    • Then dfs(0, 0, 1): Remove two 2s together for (1 + 1)² = 4 points
    • Total: 1 + 4 = 5 points
  • Best for dfs(0, 2, 0) is 5 points
  • So direct removal total: 5 + 1 = 6 points

Final Result: Both strategies give us 6 points as the maximum.

The key insight demonstrated here is how the merge strategy allows us to "save" boxes of the same color (the two 1s) to remove them together later for more points (2² = 4) instead of removing them separately (1² + 1² = 2). This dynamic programming approach explores all possible removal orders efficiently through memoization.

Solution Implementation

1class Solution:
2    def removeBoxes(self, boxes: List[int]) -> int:
3        """
4        Remove boxes to maximize points. When removing k consecutive boxes of the same color,
5        you get k * k points.
6      
7        Args:
8            boxes: List of integers representing box colors
9          
10        Returns:
11            Maximum points obtainable by removing all boxes
12        """
13        from functools import cache
14      
15        @cache
16        def dfs(left: int, right: int, extra_count: int) -> int:
17            """
18            Dynamic programming function to find maximum points for boxes[left:right+1]
19            with extra_count additional boxes of the same color as boxes[right] that can be
20            merged with boxes[right].
21          
22            Args:
23                left: Left boundary index (inclusive)
24                right: Right boundary index (inclusive)
25                extra_count: Number of boxes with same color as boxes[right] that were
26                            previously skipped and can be merged
27                          
28            Returns:
29                Maximum points obtainable from this subproblem
30            """
31            # Base case: no boxes left
32            if left > right:
33                return 0
34          
35            # Optimization: merge consecutive boxes of same color at the right end
36            # This reduces redundant states in memoization
37            while left < right and boxes[right] == boxes[right - 1]:
38                right -= 1
39                extra_count += 1
40          
41            # Option 1: Remove boxes[right] along with extra_count boxes of same color
42            max_points = dfs(left, right - 1, 0) + (extra_count + 1) * (extra_count + 1)
43          
44            # Option 2: Try to merge boxes[right] with boxes[mid] where they have same color
45            # Split the problem into two subproblems
46            for mid in range(left, right):
47                if boxes[mid] == boxes[right]:
48                    # Remove boxes between mid and right first, then merge boxes[mid] with boxes[right]
49                    points = (dfs(mid + 1, right - 1, 0) + 
50                             dfs(left, mid, extra_count + 1))
51                    max_points = max(max_points, points)
52          
53            return max_points
54      
55        # Calculate result for entire array
56        n = len(boxes)
57        result = dfs(0, n - 1, 0)
58      
59        # Clear cache to free memory
60        dfs.cache_clear()
61      
62        return result
63
1class Solution {
2    // Memoization table: dp[left][right][extraBoxes] stores the maximum points
3    // for boxes[left...right] with extraBoxes same-colored boxes to the right
4    private int[][][] dp;
5    private int[] boxes;
6
7    public int removeBoxes(int[] boxes) {
8        this.boxes = boxes;
9        int n = boxes.length;
10        dp = new int[n][n][n];
11        return calculateMaxPoints(0, n - 1, 0);
12    }
13
14    /**
15     * Calculate maximum points for removing boxes in range [left, right]
16     * @param left - left boundary of the range
17     * @param right - right boundary of the range
18     * @param extraCount - number of consecutive boxes with same color as boxes[right] 
19     *                     that are logically connected to the right side
20     * @return maximum points achievable
21     */
22    private int calculateMaxPoints(int left, int right, int extraCount) {
23        // Base case: no boxes in range
24        if (left > right) {
25            return 0;
26        }
27      
28        // Optimization: merge consecutive same-colored boxes at the right end
29        // This reduces redundant calculations
30        while (left < right && boxes[right] == boxes[right - 1]) {
31            right--;
32            extraCount++;
33        }
34      
35        // Return memoized result if already calculated
36        if (dp[left][right][extraCount] > 0) {
37            return dp[left][right][extraCount];
38        }
39      
40        // Option 1: Remove all boxes at the right end together
41        // Remove boxes[right] along with extraCount same-colored boxes
42        int maxPoints = calculateMaxPoints(left, right - 1, 0) + 
43                        (extraCount + 1) * (extraCount + 1);
44      
45        // Option 2: Look for boxes with same color as boxes[right] in the range
46        // and try to merge them before removal
47        for (int mid = left; mid < right; mid++) {
48            if (boxes[mid] == boxes[right]) {
49                // Remove boxes between mid and right first,
50                // then merge boxes[mid] with boxes[right] and extra boxes
51                int points = calculateMaxPoints(mid + 1, right - 1, 0) + 
52                            calculateMaxPoints(left, mid, extraCount + 1);
53                maxPoints = Math.max(maxPoints, points);
54            }
55        }
56      
57        // Memoize and return the result
58        dp[left][right][extraCount] = maxPoints;
59        return maxPoints;
60    }
61}
62
1class Solution {
2public:
3    int removeBoxes(vector<int>& boxes) {
4        int n = boxes.size();
5        // dp[left][right][count] represents the maximum points we can get 
6        // by removing boxes[left...right] with 'count' additional boxes 
7        // of the same color as boxes[right] on the right side
8        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, 0)));
9      
10        // Define recursive function with memoization
11        function<int(int, int, int)> calculateMaxPoints;
12      
13        calculateMaxPoints = [&](int left, int right, int additionalCount) -> int {
14            // Base case: no boxes in the range
15            if (left > right) {
16                return 0;
17            }
18          
19            // Optimization: merge consecutive boxes with same color at the right end
20            // This reduces redundant calculations
21            while (left < right && boxes[right] == boxes[right - 1]) {
22                right--;
23                additionalCount++;
24            }
25          
26            // Return memoized result if already calculated
27            if (dp[left][right][additionalCount] != 0) {
28                return dp[left][right][additionalCount];
29            }
30          
31            // Option 1: Remove boxes[right] along with additionalCount boxes of same color
32            // This gives us (additionalCount + 1)^2 points
33            int maxPoints = calculateMaxPoints(left, right - 1, 0) + 
34                           (additionalCount + 1) * (additionalCount + 1);
35          
36            // Option 2: Try to find boxes with same color as boxes[right] in range [left, right-1]
37            // and merge them together before removing
38            for (int mid = left; mid < right; mid++) {
39                if (boxes[mid] == boxes[right]) {
40                    // Remove boxes between mid and right first (boxes[mid+1...right-1])
41                    // Then remove boxes[left...mid] with boxes[right] and additional boxes
42                    maxPoints = max(maxPoints, 
43                                  calculateMaxPoints(mid + 1, right - 1, 0) + 
44                                  calculateMaxPoints(left, mid, additionalCount + 1));
45                }
46            }
47          
48            // Store the result in dp table for memoization
49            dp[left][right][additionalCount] = maxPoints;
50            return maxPoints;
51        };
52      
53        // Start with the entire array and no additional boxes
54        return calculateMaxPoints(0, n - 1, 0);
55    }
56};
57
1function removeBoxes(boxes: number[]): number {
2    const n = boxes.length;
3    // dp[left][right][count] represents the maximum points we can get 
4    // by removing boxes[left...right] with 'count' additional boxes 
5    // of the same color as boxes[right] on the right side
6    const dp: number[][][] = Array(n).fill(0).map(() => 
7        Array(n).fill(0).map(() => 
8            Array(n).fill(0)
9        )
10    );
11  
12    // Define recursive function with memoization
13    const calculateMaxPoints = (left: number, right: number, additionalCount: number): number => {
14        // Base case: no boxes in the range
15        if (left > right) {
16            return 0;
17        }
18      
19        // Optimization: merge consecutive boxes with same color at the right end
20        // This reduces redundant calculations
21        while (left < right && boxes[right] === boxes[right - 1]) {
22            right--;
23            additionalCount++;
24        }
25      
26        // Return memoized result if already calculated
27        if (dp[left][right][additionalCount] !== 0) {
28            return dp[left][right][additionalCount];
29        }
30      
31        // Option 1: Remove boxes[right] along with additionalCount boxes of same color
32        // This gives us (additionalCount + 1)^2 points
33        let maxPoints = calculateMaxPoints(left, right - 1, 0) + 
34                        (additionalCount + 1) * (additionalCount + 1);
35      
36        // Option 2: Try to find boxes with same color as boxes[right] in range [left, right-1]
37        // and merge them together before removing
38        for (let mid = left; mid < right; mid++) {
39            if (boxes[mid] === boxes[right]) {
40                // Remove boxes between mid and right first (boxes[mid+1...right-1])
41                // Then remove boxes[left...mid] with boxes[right] and additional boxes
42                maxPoints = Math.max(maxPoints, 
43                    calculateMaxPoints(mid + 1, right - 1, 0) + 
44                    calculateMaxPoints(left, mid, additionalCount + 1)
45                );
46            }
47        }
48      
49        // Store the result in dp table for memoization
50        dp[left][right][additionalCount] = maxPoints;
51        return maxPoints;
52    };
53  
54    // Start with the entire array and no additional boxes
55    return calculateMaxPoints(0, n - 1, 0);
56}
57

Time and Space Complexity

Time Complexity: O(n^4)

The time complexity analysis involves understanding the memoization pattern:

  • The dfs function has three parameters: i, j, and k
  • i and j range from 0 to n-1, giving us O(n^2) possible combinations
  • k represents the count of consecutive boxes equal to boxes[j] that follow position j. In the worst case, k can be at most n
  • This gives us O(n^3) possible states to memoize

For each state (i, j, k):

  • The while loop at the beginning runs in O(n) time in the worst case
  • The for loop iterates through positions from i to j-1, which is O(n) iterations
  • Each iteration makes recursive calls that are already memoized or will be memoized

Therefore, the total time complexity is O(n^3) states × O(n) work per state = O(n^4)

Space Complexity: O(n^3)

The space complexity consists of:

  • The memoization cache stores up to O(n^3) states (all possible combinations of i, j, and k)
  • The recursion stack depth can go up to O(n) in the worst case when we recurse through all boxes
  • Since O(n^3) dominates O(n), the overall space complexity is O(n^3)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect State Definition - Missing the "Extra Count" Parameter

One of the most common mistakes is trying to solve this problem with a simpler DP state like dp[i][j] representing the maximum points from removing boxes in range [i, j]. This approach fails because it doesn't account for boxes outside the current range that could be merged later.

Why this fails: Consider boxes [1, 2, 1, 2]. If we just use dp[i][j]:

  • We might remove the middle [2, 1] first, getting some points
  • But we lose the opportunity to merge the two 1's together for a better score

Solution: The third parameter k (or extra_count) is crucial. It tracks boxes of the same color as boxes[j] that were "skipped over" and will be merged later. This allows the algorithm to consider strategies where we remove intermediate boxes first to create larger groups.

2. Forgetting the Optimization Step

Without the consolidation step that merges consecutive same-colored boxes:

while left < right and boxes[right] == boxes[right - 1]:
    right -= 1
    extra_count += 1

Why this matters:

  • Without this optimization, you'd have many redundant states in your memoization
  • For example, dfs(0, 5, 2) and dfs(0, 4, 3) might represent the same actual problem if boxes[4] == boxes[5]
  • This leads to exponential blowup in the number of states and makes the solution too slow

Solution: Always consolidate consecutive boxes of the same color at the boundary. This ensures each memoized state is unique and reduces the total number of states from potentially O(n^4) to O(n^3).

3. Incorrect Merging Logic

A subtle but critical mistake is incorrectly handling the merge strategy:

Wrong approach:

# INCORRECT: This doesn't properly account for the merging
for h in range(i, j):
    if boxes[h] == boxes[j]:
        ans = max(ans, dfs(i, h, k) + dfs(h + 1, j, 0))  # Wrong!

Why this fails: This approach doesn't correctly model what happens when we remove the middle section. When we remove boxes [h+1, j-1], we're left with boxes[h] that should now be adjacent to boxes[j] and the k extra boxes.

Solution: The correct formulation is:

ans = max(ans, dfs(h + 1, j - 1, 0) + dfs(i, h, k + 1))
  • First remove the middle section [h+1, j-1] completely
  • Then solve for [i, h] where boxes[h] now has k+1 additional boxes to merge with

4. Memory Limit Issues with Large Inputs

The memoization cache can grow very large (O(n^3) entries), potentially causing memory issues.

Solution:

  • Clear the cache after getting the result: dfs.cache_clear()
  • Consider using an iterative DP approach with arrays if memory is critically constrained
  • Use appropriate data types (avoid unnecessary large integers if the problem constraints allow)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More