Last updated on January 18th, 2025 at 09:49 pm

Here, we see a Remove Boxes LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Dynamic Programming

Level of Question

Hard

Remove Boxes LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “Dynamic Programming with State Compression”. This pattern involves breaking down a problem into overlapping subproblems, solving each subproblem only once, and storing the results to avoid redundant computations. The state of the problem is represented by multiple variables (i, j, extra or k), which are used to define the subproblem.

3. Code Implementation in Different Languages

3.1 Remove Boxes C++

class Solution {
public:
    int dp[102][102][102];
    int solve(int i, int j, int extra, vector<pair<int, int>> &groups)
    {
        if (i > j)
            return 0;
        if (dp[i][j][extra] != -1)
            return dp[i][j][extra];
        int ans = (groups[i].second + extra) * (groups[i].second + extra) + solve(i + 1, j, 0, groups);
        for (int g = i + 1; g <= j; g++)
            if (groups[g].first == groups[i].first)
                ans = max(ans, solve(i + 1, g - 1, 0, groups) + solve(g, j, extra + groups[i].second, groups));
        return dp[i][j][extra] = ans;
    }
    int removeBoxes(vector<int> &boxes)
    {
        int n = boxes.size();
        vector<pair<int, int>> groups;
        for (int i = 0; i < n; i++)
        {
            int j = i;
            while (i + 1 < n and boxes[i + 1] == boxes[j])
                i++;
            groups.push_back({boxes[j], i - j + 1});
        }
        memset(dp, -1, sizeof(dp));
        return solve(0, groups.size() - 1, 0, groups);
    }
};

3.2 Remove Boxes Java

class Solution {
    public int removeBoxes(int[] boxes) {
        int n = boxes.length;
        int[][][] memo = new int[n][n][n];
        return removeBoxesSub(boxes, 0, n - 1, 0, memo);
    }
    private int removeBoxesSub(int[] boxes, int i, int j, int k, int[][][] memo) {
        if (i > j) return 0;
        if (memo[i][j][k] > 0) return memo[i][j][k]; 
        int tmpi = i, tmpk = k;
        while (i + 1 <= j && boxes[i + 1] == boxes[i]) {
            i++;
            k++;
        }
        int res = (k + 1) * (k + 1) + removeBoxesSub(boxes, i + 1, j, 0, memo);
        for (int m = i + 1; m <= j; m++) {
            if (boxes[i] == boxes[m]) {
                res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, memo) + removeBoxesSub(boxes, m, j, k + 1, memo));
            }
        }
        memo[tmpi][j][tmpk] = res;
        return res;
    }
}

3.3 Remove Boxes JavaScript

var removeBoxes = function (boxes) {
  const merged = []
  const points = []
  let count = 1
 
  for (let i = 0; i < boxes.length; i++) {
    if (boxes[i] !== boxes[i + 1]) {
      merged.push(boxes[i])
      points.push(count)
      count = 1
      continue
    }
    count++
  }

  const size = merged.length;
  const dp = Array.from({ length: size }, () => Array.from({ length: size }, () => new Uint16Array(boxes.length)))
  const calculate = (l, r, p) => {
    if (l > r) {
        return 0
    }
    if (dp[l][r][p]) {
        return dp[l][r][p]
    }
    let point = points[l] + p
    let max = point * point + calculate(l + 1, r, 0)
    for (let i = l + 1; i <= r; i++) {
      if (merged[i] === merged[l]) {
        max = Math.max(max, calculate(l + 1, i - 1, 0) + calculate(i, r, point))
      }
    }
    dp[l][r][p] = max
    return max
  }
  return calculate(0, size - 1, 0)
}

3.4 Remove Boxes Python

class Solution(object):
    def removeBoxes(self, boxes):
        def dp(i, j, k):
            if i > j:
                return 0
            while i < j and boxes[j] == boxes[j-1]:
                j -= 1
                k += 1
            if i == j:
                return (k+1)**2
            ans = (k+1)**2 + dp(i, j-1, 0)
            for m in range(j-1, i-1, -1):
                if boxes[m] == boxes[j]:
                    ans = max(ans, dp(i, m, k+1) + dp(m+1, j-1, 0))
            return ans
        return dp(0, len(boxes)-1, 0)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n4)	O(n3)
Java	O(n4)	O(n3)
JavaScript	O(n4)	O(n3)
Python	O(n4)	O(n3)