Remove Boxes Solution in Java

Explore Other Solutions

Problem Description

Ah, the classic “Remove Boxes” problem! Imagine you’re at a party, and you’ve got a bunch of boxes stacked up, each containing a different flavor of candy. Your goal? To remove these boxes in such a way that you maximize your candy score. Sounds easy, right? Well, here’s the catch: you can only remove boxes that are adjacent and of the same color, and for every box you remove, you get points based on how many boxes of that color you’ve just removed.

So, if you think you can just grab a handful of boxes and call it a day, think again! You need to strategize like a chess master, planning your moves ahead to ensure you get the most candy possible.

Code Solution


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];
  }
}

Approach

The approach used in this solution is a dynamic programming technique. The idea is to use a 3D memoization array to store the results of subproblems, which helps in avoiding redundant calculations. The function removeBoxes recursively calculates the maximum score by considering different segments of the boxes and the number of boxes of the same color that can be removed together.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n^3)
Space Complexity	O(n^3)

Real-World Example

Imagine you’re at a candy store, and you see a shelf filled with colorful boxes of chocolates. You can only take boxes that are next to each other and of the same flavor. The more boxes you take at once, the more points you score! But if you take a box of a different flavor, you lose your chance to score big. This is exactly what the "Remove Boxes" problem is about—strategizing your moves to maximize your candy haul!