Last updated on October 9th, 2024 at 06:13 pm

Here, We see Remove Boxes LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Remove Boxes LeetCode Solution

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

1. Remove Boxes LeetCode Solution 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);
    }
};

2. Remove Boxes LeetCode Solution 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. Remove Boxes Solution 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)
}

4. Remove Boxes Solution 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)