Remove Boxes - Practice Coding Problems

Remove Boxes - 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.

Input & Output

Example 1 — Strategic Grouping

$ Input: boxes = [1,3,2,2,2,3,4,3,1]

› Output: 23

💡 Note: Remove [2,2,2] first (9 points), then [3,3,3] becomes consecutive (9 points), then [1] (1 point), [4] (1 point), [1] (1 point). Total: 9 + 9 + 1 + 1 + 1 = 21. But optimal is actually removing in order to get [3,3] then single [3] to group later.

Example 2 — Simple Case

$ Input: boxes = [1,1,1]

› Output: 9

💡 Note: All boxes are the same color. Remove all three at once: 3² = 9 points.

Example 3 — No Grouping Possible

$ Input: boxes = [1,2,3,4,5]

› Output: 5

💡 Note: All boxes are different colors, so we can only remove them one by one: 1² + 1² + 1² + 1² + 1² = 5 points.

Constraints

1 ≤ boxes.length ≤ 100
1 ≤ boxes[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of colored boxes with removal rules

Strategy

Group same colors for k² bonus points

Output

Maximum possible points

Key Takeaway

🎯 Key Insight: Strategic removal order can group distant same-colored boxes together for exponentially higher scores

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that sometimes it's optimal to remove other boxes first to group same-colored boxes together for higher k² scores. The best approach uses 3D Dynamic Programming with memoization where dp[l][r][k] represents the maximum points from range [l,r] with k additional boxes of the same color as boxes[l]. Time: O(n⁴), Space: O(n³).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n⁴)	O(n³)	Cache results of subproblems to avoid recomputation
3D Dynamic Programming	O(n⁴)	O(n³)	Optimal DP solution with 3D state space
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible ways to remove consecutive same-colored boxes

Memoization (Top-Down DP) — Algorithm Steps

Define recursive function with memoization
For each range, try removing each consecutive group
Cache results to avoid recomputation
Return maximum points from all cached results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100
#define MAX_STATES 1000000

typedef struct {
    int l, r, k, value;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;
int boxes[MAX_N];

int findMemo(int l, int r, int k) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].l == l && memo[i].r == r && memo[i].k == k) {
            return memo[i].value;
        }
    }
    return -1;
}

void addMemo(int l, int r, int k, int value) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].l = l;
        memo[memoSize].r = r;
        memo[memoSize].k = k;
        memo[memoSize].value = value;
        memoSize++;
    }
}

int dp(int l, int r, int k) {
    if (l > r) return 0;
    
    int cached = findMemo(l, r, k);
    if (cached != -1) return cached;
    
    // Find consecutive boxes of same color starting from left
    while (l < r && boxes[l] == boxes[l + 1]) {
        l++;
        k++;
    }
    
    // Remove all boxes[l] and similar boxes on the left
    int result = (k + 1) * (k + 1) + dp(l + 1, r, 0);
    
    // Try to find boxes[l] in the middle and group them
    for (int m = l + 1; m <= r; m++) {
        if (boxes[m] == boxes[l]) {
            int option = dp(l + 1, m - 1, 0) + dp(m, r, k + 1);
            if (option > result) result = option;
        }
    }
    
    addMemo(l, r, k, result);
    return result;
}

int solution(int* inputBoxes, int len) {
    for (int i = 0; i < len; i++) {
        boxes[i] = inputBoxes[i];
    }
    memoSize = 0;
    return dp(0, len - 1, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int boxesInput[MAX_N];
    int len = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        boxesInput[len++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(boxesInput, len));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Three nested loops for start, end, and middle positions, plus one for consecutive counting

✓ Linear Growth

Space Complexity

O(n³)

Memoization table stores results for all possible range combinations

⚠ Quadratic Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen