Scale Engineer

Remove Boxes

Hard
#0530Time: Exponential, likely O(n * n!). At each step in the recursion, there can be up to `n` choices for which block to remove. This creates a vast search tree of possibilities, making it infeasible for the given constraints.Space: O(n^2). The recursion can go up to `n` levels deep. In each recursive call, a new list of boxes might be created, which can have a size up to `n`. This leads to a space complexity of `O(n*n)` in the worst case.3 companies
Patterns
Dynamic ProgrammingMemoization
Data structures
Array
Companies
CiscoCapital OneTencent

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible sequence of box removals. At each step, any continuous block of same-colored boxes can be removed. The algorithm recursively explores the consequences of each possible removal, calculating the score for the remaining boxes. The final answer is the maximum score found among all explored paths.

Algorithm

  • Define a recursive function solve(current_boxes) that takes a list of integers representing the current state of boxes.
  • The base case for the recursion is when current_boxes is empty, in which case it returns 0.
  • Initialize a variable max_points to 0 to keep track of the maximum score achievable from the current state.
  • Iterate through the current_boxes list from left to right. For each position i, identify the contiguous block of same-colored boxes starting at i. Let this block end at index j.
  • The size of this block is k = j - i + 1.
  • Create a new list, next_boxes, by removing the block from i to j from current_boxes.
  • Make a recursive call solve(next_boxes) and add the score for the current removal, k*k, to its result.
  • Update max_points = max(max_points, k*k + solve(next_boxes)).
  • To avoid re-evaluating the same sub-block, advance the iterator i to j+1 after processing the block.
  • The function returns max_points.

Walkthrough

The core idea is to define a recursive function, say calculate(boxes_list), that takes the current list of boxes as input. In this function, we iterate through the list to find all continuous blocks of same-colored boxes. For each block found (e.g., k boxes starting at index i), we calculate the points for removing it (k*k). We then create a new list of boxes by removing this block and make a recursive call calculate(new_boxes_list) to find the maximum score for the rest of the boxes. The total score for this choice is k*k + calculate(new_boxes_list). We keep track of the maximum score found among all possible block removals at the current step. The base case for the recursion is an empty list of boxes, for which the score is 0. This method is very inefficient because it recalculates scores for the same sub-configurations of boxes multiple times.

// This is a conceptual illustration. A direct implementation is complex due to list manipulations// and would be extremely slow, likely causing a Time Limit Exceeded error.// For this reason, a full, runnable code snippet is omitted./*public int solve(List<Integer> boxes) {    if (boxes.isEmpty()) {        return 0;    }    int maxScore = 0;    for (int i = 0; i < boxes.size(); ) {        int j = i;        while (j + 1 < boxes.size() && boxes.get(j + 1).equals(boxes.get(i))) {            j++;        }        int k = j - i + 1;        List<Integer> nextBoxes = new ArrayList<>(boxes.subList(0, i));        nextBoxes.addAll(boxes.subList(j + 1, boxes.size()));                int currentScore = k * k + solve(nextBoxes);        maxScore = Math.max(maxScore, currentScore);                i = j + 1;    }    return maxScore;}*/

Complexity

Time

Exponential, likely O(n * n!). At each step in the recursion, there can be up to `n` choices for which block to remove. This creates a vast search tree of possibilities, making it infeasible for the given constraints.

Space

O(n^2). The recursion can go up to `n` levels deep. In each recursive call, a new list of boxes might be created, which can have a size up to `n`. This leads to a space complexity of `O(n*n)` in the worst case.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error for most inputs beyond a very small size.

  • Repeatedly solves the same subproblems, as it lacks memoization.

Solutions

class Solution { private int [][][] f ; private int [] b ; public int removeBoxes ( int [] boxes ) { b = boxes ; int n = b . length ; f = new int [ n ][ n ][ n ]; return dfs ( 0 , n - 1 , 0 ); } private int dfs ( int i , int j , int k ) { if ( i > j ) { return 0 ; } while ( i < j && b [ j ] == b [ j - 1 ]) { -- j ; ++ k ; } if ( f [ i ][ j ][ k ] > 0 ) { return f [ i ][ j ][ k ]; } int ans = dfs ( i , j - 1 , 0 ) + ( k + 1 ) * ( k + 1 ); for ( int h = i ; h < j ; ++ h ) { if ( b [ h ] == b [ j ]) { ans = Math . max ( ans , dfs ( h + 1 , j - 1 , 0 ) + dfs ( i , h , k + 1 )); } } f [ i ][ j ][ k ] = ans ; return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem