We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Boxes

Number: 546

Difficulty: Hard

Paid? No

Companies: Capital One, Google, Cisco, Bloomberg, Tencent

Problem Description

Given an array of boxes where each box is represented by a positive integer (its color), you need to remove the boxes in rounds. In each round, you remove a contiguous sequence of boxes that have the same color and earn points equal to the square of the number of boxes removed. The goal is to determine the maximum points obtainable by strategically ordering the removals.

Key Insights

  • This is a hard optimization problem with overlapping sub-problems.
  • The heart of the solution is dynamic programming with memoization.
  • The key is to consider not just the boxes between indices l and r, but also how many same-colored boxes adjacent to the segment can be combined (parameter k).
  • Use a 3-dimensional DP state dp(l, r, k) representing the maximum points achievable from range [l, r] with k extra boxes (of the same color as box l) appended from the left.
  • When the first box has consecutive boxes of the same color, they can be aggregated to simplify the state.
  • Properly splitting the array at optimal positions where a future same-colored box appears is essential to combine points.

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case scenario due to the three nested parameters (l, r, and k), where n is the length of boxes. Space Complexity: O(n^3) for memoization storage.

Solution

The solution uses recursion with memoization (a top-down dynamic programming approach). For a subarray from index l to r with k extra boxes of the same color as boxes[l] appended, calculate the maximum points as follows:

  1. First, merge all consecutive boxes at the beginning that are the same as boxes[l] by increasing k and moving l forward.
  2. Remove the merged block immediately and calculate points as (k+1)^2 plus the result of solving the remaining subarray.
  3. Try to find any index m in [l+1, r] where boxes[m] equals boxes[l]. By not removing boxes[l] immediately, we first remove the boxes in between (l+1 to m-1) and then merge boxes[l] with boxes[m]. This may yield a higher score.
  4. Use memoization to avoid repeated calculations for the same state (l, r, k).

The trick is in the merge step that optimally leverages same-colored boxes that are separated by other boxes.

Code Solutions

# Python solution using recursion with memoization
class Solution:
    def removeBoxes(self, boxes):
        # memo dictionary to store computed values for state (l, r, k)
        memo = {}
        
        def dp(l, r, k):
            # Base case: no boxes left
            if l > r:
                return 0
            # Check memoized result
            if (l, r, k) in memo:
                return memo[(l, r, k)]
            
            # Increase l and k if consecutive boxes are the same as boxes[l]
            orig_l, orig_k = l, k
            while l + 1 <= r and boxes[l+1] == boxes[l]:
                l += 1
                k += 1
            
            # Remove the boxes[l] block, get (k+1)^2 points, then solve for the rest
            result = (k+1)**2 + dp(l+1, r, 0)
            
            # Try to merge non-adjacent boxes that are the same as boxes[l]
            for m in range(l+1, r+1):
                if boxes[m] == boxes[l]:
                    # Combine boxes[l] with boxes[m] after clearing boxes in between
                    temp = dp(l+1, m-1, 0) + dp(m, r, k+1)
                    if temp > result:
                        result = temp
            
            memo[(orig_l, r, orig_k)] = result
            return result
        
        return dp(0, len(boxes)-1, 0)
← Back to All Questions