Get started

Remove Boxes — Hard Problem & Solution

A row of boxes is given, boxes[i] being the colour of the i-th box.

Problem statement

A row of boxes is given, boxes[i] being the colour of the i-th box. In each round you remove one maximal group of k >= 1 adjacent boxes of the same colour and score k * k points; the boxes on either side then become adjacent. You keep going until no boxes remain.

Return the maximum total score you can get.

Example 1

Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation: Remove `[2,2,2]` (9), then the single 4 (1), then `[3,3,3]` (9), then `[1,1]` (4).

Example 2

Input: boxes = [1,1,1]
Output: 9

Example 3

Input: boxes = [5]
Output: 1

Constraints

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

How to solve Remove Boxes

A three-dimensional interval DP. The extra index k records how many boxes of the left end's colour have been saved up to be removed together with it, which is exactly the information plain dp(l, r) loses.

Approach

  1. dp(l, r, k) = maximum points for boxes[l..r] with k extra boxes of colour boxes[l] attached on the left; dp(l, r, k) = 0 when l > r.
  2. Option 1: remove the left group now — (k + 1)^2 + dp(l + 1, r, 0).
  3. Option 2: for each m in l + 1..r with boxes[m] == boxes[l], clear the middle first and merge — dp(l + 1, m - 1, 0) + dp(m, r, k + 1).
  4. Take the maximum, memoise it, and return dp(0, n - 1, 0).

Why it works

Consider the round in which box l disappears. Either it is removed with only its k attached companions (option 1), or it is removed together with some later box of the same colour; letting m be the first such box, everything strictly between them must have been removed before, independently of the rest (option 2). These cases cover every strategy, and each subproblem is again of the same form.

Complexity

  • Time — O(n^4) worst case (n^3 states, O(n) transitions)
  • Space — O(n^3)

Pitfalls

  • A two-index dp(l, r) cannot express the merge bonus and gives wrong answers.
  • The score is k * k for the group removed in one round, not one point per box.
  • Memoise all three indices — without it the recursion is exponential.

Reference solution

Python

import sys
from typing import List

def removeBoxes(boxes: List[int]) -> int:
    sys.setrecursionlimit(10000)
    n = len(boxes)
    memo = {}

    def dp(l, r, k):
        if l > r:
            return 0
        key = (l * 128 + r) * 128 + k
        if key in memo:
            return memo[key]
        best = (k + 1) * (k + 1) + dp(l + 1, r, 0)
        for m in range(l + 1, r + 1):
            if boxes[m] == boxes[l]:
                cand = dp(l + 1, m - 1, 0) + dp(m, r, k + 1)
                if cand > best:
                    best = cand
        memo[key] = best
        return best

    return dp(0, n - 1, 0)

JavaScript

var removeBoxes = function(boxes) {
    var n = boxes.length;
    var memo = new Int32Array(n * n * n).fill(-1);
    var dp = function(l, r, k) {
        if (l > r) return 0;
        var key = (l * n + r) * n + k;
        if (memo[key] >= 0) return memo[key];
        var best = (k + 1) * (k + 1) + dp(l + 1, r, 0);
        for (var m = l + 1; m <= r; m++) {
            if (boxes[m] === boxes[l]) {
                var cand = dp(l + 1, m - 1, 0) + dp(m, r, k + 1);
                if (cand > best) best = cand;
            }
        }
        memo[key] = best;
        return best;
    };
    return dp(0, n - 1, 0);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming