546. Remove Boxes LeetCode Solution

In this guide, you will get 546. Remove Boxes LeetCode Solution with the best time and space complexity. The solution to Remove Boxes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Remove Boxes solution in C++
Remove Boxes solution in Java
Remove Boxes solution in Python
Additional Resources

546. Remove Boxes LeetCode Solution image

Problem Statement of Remove Boxes

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

Complexity Analysis

Time Complexity: O(n^4)
Space Complexity: O(n^3)

546. Remove Boxes LeetCode Solution in C++

class Solution {
 public:
  int removeBoxes(vector<int>& boxes) {
    const int n = boxes.size();
    vector<vector<vector<int>>> mem(n, vector<vector<int>>(n, vector<int>(n)));
    return removeBoxes(boxes, 0, n - 1, 0, mem);
  }

 private:
  // Returns the maximum score of boxes[i..j] if k boxes eqaul to boxes[j].
  int removeBoxes(const vector<int>& boxes, int i, int j, int k,
                  vector<vector<vector<int>>>& mem) {
    if (i > j)
      return 0;
    if (mem[i][j][k] > 0)
      return mem[i][j][k];

    int r = j;
    int sameBoxes = k + 1;
    while (r > 0 && boxes[r - 1] == boxes[r]) {
      --r;
      ++sameBoxes;
    }
    mem[i][j][k] = removeBoxes(boxes, i, r - 1, 0, mem) + sameBoxes * sameBoxes;

    for (int p = i; p < r; ++p)
      if (boxes[p] == boxes[r])
        mem[i][j][k] =
            max(mem[i][j][k], removeBoxes(boxes, i, p, sameBoxes, mem) +
                                  removeBoxes(boxes, p + 1, r - 1, 0, mem));

    return mem[i][j][k];
  }
};
/* code provided by PROGIEZ */

546. Remove Boxes LeetCode Solution in Java

class Solution {
  public int removeBoxes(int[] boxes) {
    final int n = boxes.length;
    int[][][] mem = new int[n][n][n];
    return removeBoxes(boxes, 0, n - 1, 0, mem);
  }

  // Returns the maximum score of boxes[i..j] if k boxes are equal to boxes[j]
  private int removeBoxes(int[] boxes, int i, int j, int k, int[][][] mem) {
    if (i > j)
      return 0;
    if (mem[i][j][k] > 0)
      return mem[i][j][k];

    int r = j;
    int sameBoxes = k + 1;
    while (r > 0 && boxes[r - 1] == boxes[r]) {
      --r;
      ++sameBoxes;
    }
    mem[i][j][k] = removeBoxes(boxes, i, r - 1, 0, mem) + sameBoxes * sameBoxes;

    for (int p = i; p < r; ++p)
      if (boxes[p] == boxes[r])
        mem[i][j][k] = Math.max(mem[i][j][k], removeBoxes(boxes, i, p, sameBoxes, mem) +
                                                  removeBoxes(boxes, p + 1, r - 1, 0, mem));

    return mem[i][j][k];
  }
}
// code provided by PROGIEZ

546. Remove Boxes LeetCode Solution in Python

class Solution:
  def removeBoxes(self, boxes: list[int]) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> int:
      """
      Returns the maximum score of boxes[i..j] if k boxes equal to boxes[j].
      """
      if i > j:
        return 0

      r = j
      sameBoxes = k + 1
      while r > 0 and boxes[r - 1] == boxes[r]:
        r -= 1
        sameBoxes += 1
      res = dp(i, r - 1, 0) + sameBoxes * sameBoxes

      for p in range(i, r):
        if boxes[p] == boxes[r]:
          res = max(res, dp(i, p, sameBoxes) + dp(p + 1, r - 1, 0))

      return res

    return dp(0, len(boxes) - 1, 0)
 # code by PROGIEZ