LeetCode 546: Remove Boxes Solution

Master LeetCode problem 546 (Remove Boxes), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

546. Remove Boxes

Hard

Array Dynamic Programming Memoization

Problem Explanation

Explanation

The given problem can be solved using dynamic programming. We can define a function dp(i, j, k) that represents the maximum points that can be obtained by removing boxes from index i to index j while having k boxes of the same color as box i appended at the end. The key insight is to consider the possibilities of different cases when removing boxes.

If the k boxes are attached to box i, we can remove them at the same time to get k*k points plus the maximum points from dp(i+1, j, 1).
For each middle box m between i and j, if box i and m have the same color, we can consider the possibility of removing box i later after removing boxes from m+1 to j to get more points.
For the case where there is no box with the same color as box i, we can simply remove box i and its adjacent boxes from i+1 to j first to get dp(i+1, j, 1) points.

By considering all these possibilities, we can build our dynamic programming solution to find the maximum points.

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

Solution Code

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

    private int calculatePoints(int[] boxes, int[][][] dp, int i, int j, int k) {
        if (i > j) return 0;
        if (dp[i][j][k] != 0) return dp[i][j][k];

        while (i + 1 <= j && boxes[i] == boxes[i + 1]) {
            i++;
            k++;
        }
        
        int points = (k + 1) * (k + 1) + calculatePoints(boxes, dp, i + 1, j, 0);

        for (int m = i + 1; m <= j; m++) {
            if (boxes[i] == boxes[m]) {
                points = Math.max(points, calculatePoints(boxes, dp, i + 1, m - 1, 0) + calculatePoints(boxes, dp, m, j, k + 1));
            }
        }

        dp[i][j][k] = points;
        return points;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 546 (Remove Boxes)?

This page provides optimized solutions for LeetCode problem 546 (Remove Boxes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 546 (Remove Boxes)?

The time complexity for LeetCode 546 (Remove Boxes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 546 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 546 in Java, C++, or Python.

Back to LeetCode Solutions