You are given several boxes with different colors represented by different positive numbers.
You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= 1), remove them and get k * k points.
Return the maximum points you can get.
Example 1:
Input: boxes = [1,3,2,2,2,3,4,3,1] Output: 23 Explanation: [1, 3, 2, 2, 2, 3, 4, 3, 1] ----> [1, 3, 3, 4, 3, 1] (3*3=9 points) ----> [1, 3, 3, 3, 1] (1*1=1 points) ----> [1, 1] (3*3=9 points) ----> [] (2*2=4 points)
Example 2:
Input: boxes = [1,1,1] Output: 9
Example 3:
Input: boxes = [1] Output: 1
Constraints:
1 <= boxes.length <= 1001 <= boxes[i] <= 100Problem Overview: You are given an array where each value represents a colored box. Removing k adjacent boxes of the same color gives k * k points. After removal the array collapses. The challenge is choosing the removal order that maximizes total score.
Approach 1: Brute Force Recursion (Exponential Time, O(n) Space)
The naive idea is to try every possible group of equal adjacent boxes, remove it, and recursively solve the remaining array. Each removal changes the structure of the array, so the recursion branches heavily. This explores all valid removal orders and returns the best score. The method quickly becomes infeasible because the number of states grows exponentially with n. It helps build intuition but cannot pass large constraints.
Approach 2: Recursive Dynamic Programming with Memoization (O(n^4) Time, O(n^3) Space)
The key insight is that removing boxes later can produce a larger group if matching colors are preserved. Define a DP state dp(l, r, k) where l and r define the current subarray and k represents how many boxes equal to boxes[r] are attached to the right side. First compress consecutive equal boxes at the end. One option removes the group immediately: dp(l, r-1, 0) + (k+1)^2. Another option merges it with a matching color earlier in the array by splitting at index i where boxes[i] == boxes[r]. Memoizing these states avoids recomputation and turns the exponential search into polynomial time. This approach relies heavily on dynamic programming and memoization to store overlapping subproblems.
Approach 3: Iterative Dynamic Programming (O(n^4) Time, O(n^3) Space)
The same state transition can be implemented bottom‑up. Build a 3D DP table where dp[l][r][k] represents the maximum score for the interval [l, r] with k extra boxes equal to boxes[r]. Iterate over increasing subarray lengths and compute transitions based on removing the last group or merging with a matching color earlier in the interval. The iterative version avoids recursion overhead and works well in languages like C++. The algorithm still performs nested loops over indices and merge positions, giving O(n^4) time complexity.
Recommended for interviews: Interviewers expect the recursive DP with memoization solution. It demonstrates understanding of state compression and interval dynamic programming. Explaining why the extra parameter k is required shows deeper insight. Brute force demonstrates the search space, but the memoized DP shows the optimization skill expected for hard problems.
This approach uses recursion and memoization to compute the maximum score recursively. We artificially modify the problem to keep count of contiguous boxes and use a 3D array for memoization. The base case is when there are no boxes left. Recurrence relations deal with choosing to remove a contiguous segment immediately or merge it with other parts of the array by considering different partition points.
The recursive dp function tries to match different segments of the array and calculates scores accordingly. dp(l, r, k) computes the maximum score for a subarray while considering preprocessing contiguous blocks at index r. By reducing r to a point where we have a different color or run out of elements to compare, we explore subproblems and store results in the memoization table to save on future calculations.
Python
JavaScript
Time Complexity: O(n^4). The recursive solution has three dimensions for recursion state, each from 0 to n.
Space Complexity: O(n^3). Needed for memoization storage.
This approach converts the recursive problem into an iterative dynamic programming solution. We maintain a 3D table to determine maximum obtainable points for different contiguous subarrays and contingent blocks for each color. We fill the table starting from smaller segments and incrementally consider larger segments while determining scores.
The solution populates a 3D dp table by fixing lengths and starting index l of segments before solving larger segments. For each possible partition index m where blocks match color l of the segments, scores are merged and computed effectively. The iterative solution ensures no recursion overhead and efficiently computes all subproblem solutions iteratively.
C++
Time Complexity: O(n^4). Similar state iterations but performed iteratively.
Space Complexity: O(n^3). Space used for the iterative 3D table.
| Approach | Complexity |
|---|---|
| Recursive Dynamic Programming with Memoization | Time Complexity: O(n^4). The recursive solution has three dimensions for recursion state, each from 0 to n. |
| Iterative Dynamic Programming | Time Complexity: O(n^4). Similar state iterations but performed iteratively. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | Exponential | O(n) | Conceptual baseline to understand all possible removal orders |
| Recursive DP with Memoization | O(n^4) | O(n^3) | General optimal solution used in interviews and most editorial explanations |
| Iterative 3D Dynamic Programming | O(n^4) | O(n^3) | When recursion depth is a concern or implementing bottom-up DP in C++ |
Leetcode Remove Boxes | Codeforces Div2 E: 2400 | Vasya and Binary String • Kartik Arora • 14,307 views views
Watch 9 more video solutions →Practice Remove Boxes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor