LeetCode 546 - Remove Boxes

The problem gives us an array called boxes, where each integer represents the color of a box. We may repeatedly remove groups of adjacent boxes that share the same color. If we remove a group containing k boxes, we earn k k points.

leetcodehardarraydynamic-programmingmemoization

LeetCode Problem 546

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Memoization

Solution

LeetCode 546, Remove Boxes

Problem Understanding

The problem gives us an array called boxes, where each integer represents the color of a box. We may repeatedly remove groups of adjacent boxes that share the same color. If we remove a group containing k boxes, we earn k * k points.

The important detail is that removing boxes changes the structure of the array. Boxes that were previously separated may become adjacent after intermediate boxes are removed. This means the order in which we remove groups matters significantly.

The goal is to maximize the total score after all boxes are removed.

For example, suppose we have:

[1,3,2,2,2,3,4,3,1]

If we remove the three adjacent 2s first, we gain 3 * 3 = 9 points. After they disappear, the remaining array becomes:

[1,3,3,4,3,1]

Now more opportunities appear because some equal colors have become closer together.

The constraints are important:

  • 1 <= boxes.length <= 100
  • 1 <= boxes[i] <= 100

An array size of 100 is too large for brute force enumeration of all possible removal sequences. The number of different ways to remove groups grows explosively because every removal changes future possibilities.

This immediately suggests that we need dynamic programming with memoization.

Several edge cases are especially important:

  • Arrays containing only one color, where removing everything at once is optimal.
  • Arrays where equal colors are separated by other colors.
  • Arrays with alternating colors, where merging equal values later may produce higher scores.
  • Very small arrays such as length 1.
  • Situations where removing a smaller group first allows a much larger merged group later.

The main challenge is that the locally optimal move is often not globally optimal.

Approaches

Brute Force Approach

A brute force solution would recursively try every possible removable group at every step.

At any point:

  1. Find every contiguous segment of equal values.
  2. Remove one segment.
  3. Recursively solve the remaining array.
  4. Return the maximum score among all choices.

This approach is correct because it explores every possible removal order. Eventually, it discovers the optimal sequence.

However, it is far too slow. Every removal creates a new array configuration, and the number of possible sequences grows exponentially. Since the array length can reach 100, brute force becomes completely impractical.

The core issue is overlapping subproblems. The same remaining configurations appear repeatedly during recursion.

Key Insight for the Optimal Solution

The difficult part of this problem is that it may be beneficial to delay removing some boxes so they can merge with matching boxes later.

Consider:

[1, 2, 1]

If we remove the first 1 immediately:

  • Remove 1, gain 1
  • Remove 2, gain 1
  • Remove 1, gain 1
  • Total = 3

But if we remove 2 first:

  • Remove 2, gain 1
  • Array becomes [1,1]
  • Remove both 1s together, gain 4
  • Total = 5

This means the DP state must remember not only the current subarray, but also how many equal-colored boxes are already grouped with one side.

The standard solution uses a 3D dynamic programming state:

dp(left, right, count)

This means:

  • We are solving the subarray boxes[left:right+1]
  • There are already count extra boxes equal to boxes[left] attached to the left side

This additional parameter is the key insight that makes the problem solvable.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries every possible removal sequence
Optimal O(n^4) O(n^3) Memoized interval DP with carry count

Algorithm Walkthrough

Optimal Dynamic Programming Strategy

We define:

dp(left, right, count)

where:

  • left and right define the current interval
  • count represents how many extra boxes equal to boxes[left] are grouped together with boxes[left]

The function returns the maximum score obtainable from this interval.

Step by Step Process

  1. Define the recursive state.

We solve the problem for a subarray boxes[left:right+1]. The parameter count tracks additional boxes matching boxes[left] that were merged from outside the interval.

This is necessary because larger groups produce disproportionately larger scores. 2. Handle the base case.

If:

left > right

then there are no boxes remaining, so the score is 0. 3. Compress consecutive equal boxes at the beginning.

Suppose we have:

[2,2,2,3,...]

Instead of treating these separately, we immediately merge them into the carry count.

For example:

dp(left, right, count)

becomes:

dp(newLeft, right, count + mergedCount)

This optimization reduces repeated states. 4. Compute the direct removal option.

One possibility is to remove the current group immediately.

If the current merged group size is:

count + 1

then removing it gives:

(count + 1)^2

plus the optimal score for the remaining interval. 5. Try merging with matching boxes later.

We scan the interval looking for positions where:

boxes[mid] == boxes[left]

If such a position exists, we can:

  • Remove everything between them first
  • Then merge the matching boxes into a larger group

This often produces a better score. 6. Take the maximum result.

The DP state returns the best score among:

  • Removing immediately
  • Delaying removal to merge later
  1. Memoize results.

Since many recursive calls repeat the same states, memoization avoids recomputation.

Why it works

The algorithm works because every optimal strategy for an interval must eventually choose one of two possibilities for the leading group:

  • Remove it immediately
  • Merge it with a matching box later

The DP explores both possibilities exhaustively while memoization guarantees each unique state is solved only once. The carry parameter preserves all information needed to make optimal future decisions, so the recursion always computes the true optimal score.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        n = len(boxes)

        @lru_cache(None)
        def dp(left: int, right: int, count: int) -> int:
            if left > right:
                return 0

            # Merge consecutive equal boxes
            while left < right and boxes[left] == boxes[left + 1]:
                left += 1
                count += 1

            # Option 1:
            # Remove current group immediately
            best = (count + 1) * (count + 1) + dp(left + 1, right, 0)

            # Option 2:
            # Merge with future matching boxes
            for mid in range(left + 1, right + 1):
                if boxes[mid] == boxes[left]:
                    score = (
                        dp(left + 1, mid - 1, 0)
                        + dp(mid, right, count + 1)
                    )
                    best = max(best, score)

            return best

        return dp(0, n - 1, 0)

The implementation follows the recursive interval DP structure directly.

The dp(left, right, count) function represents the optimal answer for the interval while carrying extra matching boxes.

The first while loop compresses consecutive equal values. This is an important optimization because contiguous equal boxes should always be treated as one larger group.

The variable best first stores the score obtained by removing the current group immediately.

Then the loop searches for future matching boxes. Whenever a matching color is found, the algorithm removes the middle section first so the matching groups can merge.

Memoization through @lru_cache(None) ensures each state is computed only once.

Finally, the solution starts with the entire array and no carry:

dp(0, n - 1, 0)

Go Solution

func removeBoxes(boxes []int) int {
	n := len(boxes)

	memo := make(map[[3]int]int)

	var dp func(int, int, int) int

	dp = func(left, right, count int) int {
		if left > right {
			return 0
		}

		key := [3]int{left, right, count}

		if val, exists := memo[key]; exists {
			return val
		}

		originalLeft := left
		originalCount := count

		// Merge consecutive equal boxes
		for left < right && boxes[left] == boxes[left+1] {
			left++
			count++
		}

		// Remove current group immediately
		best := (count+1)*(count+1) + dp(left+1, right, 0)

		// Try merging with future matching boxes
		for mid := left + 1; mid <= right; mid++ {
			if boxes[mid] == boxes[left] {
				score := dp(left+1, mid-1, 0) +
					dp(mid, right, count+1)

				if score > best {
					best = score
				}
			}
		}

		memo[[3]int{originalLeft, right, originalCount}] = best

		return best
	}

	return dp(0, n-1, 0)
}

The Go version uses a map[[3]int]int as the memoization structure because Go does not provide a built in memoization decorator like Python's lru_cache.

The recursive logic is otherwise identical.

Go slices are lightweight references to arrays, so passing boxes into recursive calls is efficient.

Integer overflow is not a concern because the maximum score is bounded by:

100 * 100 = 10000

which easily fits in Go's int.

Worked Examples

Example 1

Input:

[1,3,2,2,2,3,4,3,1]

Initial call:

dp(0, 8, 0)
Step Action Score
1 Remove 2,2,2 9
2 Array becomes [1,3,3,4,3,1]
3 Remove 4 1
4 Array becomes [1,3,3,3,1]
5 Remove 3,3,3 9
6 Array becomes [1,1]
7 Remove 1,1 4
Total 23

The DP discovers this sequence automatically by exploring merge opportunities.

A critical observation is that the middle 3s become more valuable after removing the 4.

Example 2

Input:

[1,1,1]

The algorithm compresses consecutive equal boxes immediately.

State progression:

State Meaning
dp(0,2,0) Start
Compress consecutive 1s count becomes 2
Remove all together (2+1)^2 = 9

Final answer:

9

Example 3

Input:

[1]

The only move is:

Step Action Score
1 Remove 1 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n^4) There are O(n^3) states, each may scan O(n) positions
Space O(n^3) Memoization table stores all DP states

The DP state consists of three dimensions:

  • left
  • right
  • count

Each can vary up to n, producing O(n^3) states.

For every state, we may scan the interval looking for matching colors, which costs O(n) time.

Therefore, the total complexity becomes:

O(n^4)

This is acceptable for n <= 100.

Test Cases

sol = Solution()

assert sol.removeBoxes([1,3,2,2,2,3,4,3,1]) == 23  # official example
assert sol.removeBoxes([1,1,1]) == 9  # all same color
assert sol.removeBoxes([1]) == 1  # single element
assert sol.removeBoxes([1,2,1]) == 5  # merging later is better
assert sol.removeBoxes([1,2,2,2,1]) == 13  # remove middle first
assert sol.removeBoxes([1,2,3,4]) == 4  # no merges possible
assert sol.removeBoxes([1,1,2,2,2,1,1]) == 25  # large merge after removal
assert sol.removeBoxes([2,2,2,2]) == 16  # one large group
assert sol.removeBoxes([1,2,1,2,1,2]) == 12  # alternating pattern
assert sol.removeBoxes([3,3,3,1,3]) == 17  # preserve merge opportunity
Test Why
[1,3,2,2,2,3,4,3,1] Validates official complex example
[1,1,1] Tests full compression of equal values
[1] Minimum input size
[1,2,1] Ensures delayed merging works
[1,2,2,2,1] Tests removing middle section first
[1,2,3,4] No merges possible
[1,1,2,2,2,1,1] Large merge formed later
[2,2,2,2] Single large group
[1,2,1,2,1,2] Alternating colors
[3,3,3,1,3] Tests carrying counts correctly

Edge Cases

Single Box

A single element array is the smallest valid input. A buggy implementation might accidentally recurse into invalid ranges or mishandle base cases.

For example:

[1]

The implementation handles this correctly because:

(left > right)

returns 0 for empty intervals, and the single box contributes:

(0 + 1)^2 = 1

All Boxes Have the Same Color

Consider:

[2,2,2,2]

The optimal strategy is obviously to remove everything at once for:

4^2 = 16

Without the consecutive compression optimization, the DP would generate many redundant states. The implementation avoids this by merging adjacent equal values immediately inside the while loop.

Equal Colors Separated by Other Colors

This is the most important edge case.

Example:

[1,2,1]

A greedy algorithm that removes the first available group would fail.

The correct solution removes the middle 2 first so the two 1s become adjacent.

The count parameter in the DP state is specifically designed to handle this situation. It allows the recursion to remember postponed groups and later merge them into larger scoring removals.