# Remove Boxes
**Difficulty:** HARD
[External](https://leetcode.com/problems/remove-boxes)
Canonical: https://scaleengineer.com/dsa/problems/remove-boxes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Capital One](https://scaleengineer.com/companies/capital-one), [Tencent](https://scaleengineer.com/companies/tencent)
---
## Problem
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 <= 100`
* `1 <= boxes[i] <= 100`

# Approaches
## Brute-Force Recursion
This approach attempts to solve the problem by exploring every possible sequence of box removals. At each step, any continuous block of same-colored boxes can be removed. The algorithm recursively explores the consequences of each possible removal, calculating the score for the remaining boxes. The final answer is the maximum score found among all explored paths.
**Time:** Exponential, likely O(n * n!). At each step in the recursion, there can be up to `n` choices for which block to remove. This creates a vast search tree of possibilities, making it infeasible for the given constraints. · **Space:** O(n^2). The recursion can go up to `n` levels deep. In each recursive call, a new list of boxes might be created, which can have a size up to `n`. This leads to a space complexity of `O(n*n)` in the worst case.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for most inputs beyond a very small size.; Repeatedly solves the same subproblems, as it lacks memoization.
### Explanation
The core idea is to define a recursive function, say `calculate(boxes_list)`, that takes the current list of boxes as input. In this function, we iterate through the list to find all continuous blocks of same-colored boxes. For each block found (e.g., `k` boxes starting at index `i`), we calculate the points for removing it (`k*k`). We then create a new list of boxes by removing this block and make a recursive call `calculate(new_boxes_list)` to find the maximum score for the rest of the boxes. The total score for this choice is `k*k + calculate(new_boxes_list)`. We keep track of the maximum score found among all possible block removals at the current step. The base case for the recursion is an empty list of boxes, for which the score is 0. This method is very inefficient because it recalculates scores for the same sub-configurations of boxes multiple times.

```java
// This is a conceptual illustration. A direct implementation is complex due to list manipulations
// and would be extremely slow, likely causing a Time Limit Exceeded error.
// For this reason, a full, runnable code snippet is omitted.
/*
public int solve(List<Integer> boxes) {
    if (boxes.isEmpty()) {
        return 0;
    }
    int maxScore = 0;
    for (int i = 0; i < boxes.size(); ) {
        int j = i;
        while (j + 1 < boxes.size() && boxes.get(j + 1).equals(boxes.get(i))) {
            j++;
        }
        int k = j - i + 1;
        List<Integer> nextBoxes = new ArrayList<>(boxes.subList(0, i));
        nextBoxes.addAll(boxes.subList(j + 1, boxes.size()));
        
        int currentScore = k * k + solve(nextBoxes);
        maxScore = Math.max(maxScore, currentScore);
        
        i = j + 1;
    }
    return maxScore;
}
*/
```
### Algorithm
- Define a recursive function `solve(current_boxes)` that takes a list of integers representing the current state of boxes.
- The base case for the recursion is when `current_boxes` is empty, in which case it returns 0.
- Initialize a variable `max_points` to 0 to keep track of the maximum score achievable from the current state.
- Iterate through the `current_boxes` list from left to right. For each position `i`, identify the contiguous block of same-colored boxes starting at `i`. Let this block end at index `j`.
- The size of this block is `k = j - i + 1`.
- Create a new list, `next_boxes`, by removing the block from `i` to `j` from `current_boxes`.
- Make a recursive call `solve(next_boxes)` and add the score for the current removal, `k*k`, to its result.
- Update `max_points = max(max_points, k*k + solve(next_boxes))`.
- To avoid re-evaluating the same sub-block, advance the iterator `i` to `j+1` after processing the block.
- The function returns `max_points`.

## Dynamic Programming with 3D Memoization
A more efficient method is to use dynamic programming with memoization. The key challenge is that the state of the problem changes in a non-trivial way when boxes are removed. To handle this, we define a state that captures not only the current subarray but also any pending boxes of the same color that could be merged. The state can be represented as `dp(i, j, k)`, which calculates the maximum points from the subarray `boxes[i...j]`, assuming there are `k` additional boxes of the same color as `boxes[i]` that can be grouped with it.
**Time:** O(n^4). There are `O(n^3)` possible states for `(l, r, k)`. For each state, the function may iterate up to `O(n)` times to find other boxes of the same color to merge with. This results in a total time complexity of `O(n^3 * n) = O(n^4)`. · **Space:** O(n^3). The primary space usage comes from the 3D memoization table of size `n x n x n`. The recursion stack depth also contributes, but it's dominated by the memoization table.
**Pros:** Guarantees finding the optimal solution by exploring all relevant choices.; Memoization prevents re-computation of the same subproblems, making it much more efficient than brute force.; It is efficient enough to pass within the time limits for the given constraints.
**Cons:** High polynomial time complexity of O(n^4) can be slow if `n` were larger.; Requires a large amount of memory, O(n^3), for the memoization table.
### Explanation
The state for our recursive function with memoization is `solve(i, j, k)`, representing the maximum points obtainable from the subarray `boxes[i...j]`, given that there are `k` boxes to the left of index `i` that have the same color as `boxes[i]`.

- **Base Case**: If `i > j`, the subarray is empty, so we return 0 points.
- **Recursive Step**: When computing `solve(i, j, k)`, we have two main choices regarding the first box, `boxes[i]`, and its `k` preceding same-colored boxes.
  1. **Remove the group now**: We can remove the contiguous block of boxes starting at `i` (say, of length `p`) along with the `k` preceding boxes. The points gained would be `(p+k)^2`. The problem then reduces to solving for the remaining subarray. 
  2. **Merge with a later group**: We can postpone removing the `boxes[i]` group and try to merge it with another block of the same color further down the array. To do this, we find another box `boxes[m]` (where `m > i`) of the same color. We then recursively calculate the maximum score obtainable by first clearing the boxes between `i` and `m`, and then solving the problem for the subarray starting at `m`, but now with an increased count of preceding boxes.

We take the maximum over all these possibilities. To avoid recomputing the same state `(i, j, k)`, we store the results in a 3D array `memo[n][n][n]`. The initial call is `solve(0, n-1, 0)`.

```java
class Solution {
    private int[][][] memo;
    private int[] boxes;

    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        this.boxes = boxes;
        this.memo = new int[n][n][n];
        return solve(0, n - 1, 0);
    }

    private int solve(int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        if (memo[l][r][k] != 0) {
            return memo[l][r][k];
        }

        int original_l = l;
        int original_k = k;

        // Optimization: group all consecutive boxes of same color as boxes[l]
        while (l + 1 <= r && boxes[l + 1] == boxes[l]) {
            l++;
            k++;
        }

        // Option 1: Remove the current group of boxes[l]
        // The group has (l - original_l + 1) boxes from the array, plus original_k from the left.
        // Total count is k + 1.
        int res = (k + 1) * (k + 1) + solve(l + 1, r, 0);

        // Option 2: Try to merge with other groups of the same color
        for (int m = l + 1; m <= r; m++) {
            if (boxes[m] == boxes[l]) {
                // If we find another box of the same color at index m,
                // we can try to remove the intermediate part (l+1, m-1)
                // and then solve for the rest, now with (k+1) boxes of color boxes[l]
                // to be grouped with boxes[m...].
                res = Math.max(res, solve(l + 1, m - 1, 0) + solve(m, r, k + 1));
            }
        }

        return memo[original_l][r][original_k] = res;
    }
}
```
### Algorithm
- Initialize a 3D memoization table `memo[n][n][n]` to store results of subproblems and avoid re-computation.
- Define a recursive function `solve(l, r, k)` which computes the max score for `boxes[l...r]` with `k` boxes of color `boxes[l]` available to the left.
- **Base Case**: If `l > r`, the subarray is empty, return 0.
- **Memoization Check**: If `memo[l][r][k]` is already computed, return the stored value.
- **Main Logic**:
  - First, an optimization: greedily find the end of the contiguous block of color `boxes[l]`. Let this block be `boxes[l...l']`. Update `k` to include the count of boxes in this block.
  - **Option 1 (Remove Now)**: Calculate the score for removing the current group of `(k+1)` boxes immediately. The score is `(k+1)^2` plus the score from the rest of the array, `solve(l'+1, r, 0)`.
  - **Option 2 (Merge Later)**: Iterate through the rest of the subarray from `m = l'+1` to `r`. If `boxes[m]` has the same color as `boxes[l]`, consider merging.
    - This path's score is the sum of points from removing the intermediate part `solve(l'+1, m-1, 0)` and then solving for the remaining part `solve(m, r, k+1)`, where `k+1` is the new count of boxes to be merged.
  - The result for `solve(l, r, k)` is the maximum of Option 1 and all possibilities from Option 2.
- Store the computed result in `memo[l][r][k]` before returning.
- The initial call to start the process is `solve(0, n-1, 0)`.

# Solutions
### Java

```java
class Solution { private int [][][] f ; private int [] b ; public int removeBoxes ( int [] boxes ) { b = boxes ; int n = b . length ; f = new int [ n ][ n ][ n ]; return dfs ( 0 , n - 1 , 0 ); } private int dfs ( int i , int j , int k ) { if ( i > j ) { return 0 ; } while ( i < j && b [ j ] == b [ j - 1 ]) { -- j ; ++ k ; } if ( f [ i ][ j ][ k ] > 0 ) { return f [ i ][ j ][ k ]; } int ans = dfs ( i , j - 1 , 0 ) + ( k + 1 ) * ( k + 1 ); for ( int h = i ; h < j ; ++ h ) { if ( b [ h ] == b [ j ]) { ans = Math . max ( ans , dfs ( h + 1 , j - 1 , 0 ) + dfs ( i , h , k + 1 )); } } f [ i ][ j ][ k ] = ans ; return ans ; } }
```

### CPP

```cpp
class Solution { public: int removeBoxes ( vector < int >& boxes ) { int n = boxes . size (); vector < vector < vector < int >>> f ( n , vector < vector < int >> ( n , vector < int > ( n ))); function < int ( int , int , int ) > dfs ; dfs = [ & ]( int i , int j , int k ) { if ( i > j ) return 0 ; while ( i < j && boxes [ j ] == boxes [ j - 1 ]) { -- j ; ++ k ; } if ( f [ i ][ j ][ k ]) return f [ i ][ j ][ k ]; int ans = dfs ( i , j - 1 , 0 ) + ( k + 1 ) * ( k + 1 ); for ( int h = i ; h < j ; ++ h ) { if ( boxes [ h ] == boxes [ j ]) { ans = max ( ans , dfs ( h + 1 , j - 1 , 0 ) + dfs ( i , h , k + 1 )); } } f [ i ][ j ][ k ] = ans ; return ans ; }; return dfs ( 0 , n - 1 , 0 ); } };
```

### Python

```python
class Solution : def removeBoxes ( self , boxes : List [ int ]) -> int : @ cache def dfs ( i , j , k ): if i > j : return 0 while i < j and boxes [ j ] == boxes [ j - 1 ]: j , k = j - 1 , k + 1 ans = dfs ( i , j - 1 , 0 ) + ( k + 1 ) * ( k + 1 ) 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 )) return ans n = len ( boxes ) ans = dfs ( 0 , n - 1 , 0 ) dfs . cache_clear () return ans
```