Remove Boxes Solution in C++

Problem Description

Ah, the classic “Remove Boxes” problem! It’s like trying to clean your room but instead of just tossing things out, you have to strategically remove boxes to maximize your score. Imagine you have a bunch of boxes stacked up, and they all have different colors. Your goal? To remove these boxes in such a way that you score the most points possible.

The catch? You can only remove boxes of the same color that are adjacent to each other. So, if you think you can just grab any box and toss it out, think again! It’s like trying to eat a pizza but only being allowed to take slices that are next to each other.

Code Solution

Copy Code

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

 private:
  int removeBoxes(const vector& boxes, int i, int j, int k,
                  vector>>& 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];
  }
};

Approach

The approach used in this solution is a dynamic programming technique. The function removeBoxes recursively calculates the maximum score by considering different segments of the boxes. It uses memoization to store previously computed results, which helps in avoiding redundant calculations. The key idea is to group boxes of the same color and maximize the score based on how many boxes you can remove in one go.

Time and Space Complexity

Time Complexity: O(n³), where n is the number of boxes. This is due to the three nested loops in the recursive function.

Space Complexity: O(n³) as well, because of the memoization table used to store results for subproblems.

Real-World Example

Imagine you’re at a party, and there are boxes of snacks everywhere. You can only take boxes that are next to each other, and the more boxes you take at once, the more points you score (or snacks you get!). If you grab a box of chips, you might want to grab the adjacent box of salsa too, because who eats chips without salsa? The goal is to maximize your snack haul while following the party rules!