Remove Boxes

  • 0

    Click here to see the full article post

  • 0

    The runtime of the code is indeed O(n^4), and the bound is tight in the worst case. Consider the following test case of 100 numbers in total:

    1, 2, 1, 2,  ... 1, 2, 1, 2 (25 copies of 1, 2) followed by
    1, 1, 1, ... 1, 1, 1 (25 copies of 1) followed by
    2, 2, 2, ... 2, 2, 2 (25 copies of 2).

    If you add a counter in the for-loop of the DP call, you will get a total number like 1547375 for such a test case, which is way more than 100^3. If n = 200, the counter is 24,866,625 vs 200^3 = 8,000,000, etc.

    However, if we ONLY loop through those boxes[i] that are equal to boxes[r], then the runtime can be proved to be O(n^3).
    This can be done via a preprocessing in O(n^3) time as well.

  • 0

    The WHILE loop should be in order to match with the solution description and be accepted:
    while (r > l && boxes[r] == boxes[r - 1]) {

  • 0

    I agree with @htrinh that the While loop should be modified accordingly. The While loop seems to be considering repetitions on the Left of the region instead of the right region.

    As a side note, to consider the question with "how many repetitions there are to the LEFT of the region", the while loop is the same as in the code, but the transition part is to be changed to:

    for (int i = r; i >= l+1; i--) {
    	if (boxes[i] == boxes[l]) {
    		dp[l][r][k] = max(dp[l][r][k], calculatePoints(boxes, dp, i,   r,   k+1) + 
    		                               calculatePoints(boxes, dp, l+1, i-1, 0));

  • 0

    The time complexity of the brute-force approach should be n!, not 2^n.
    Let f(n) be the time to find the solution of n boxes with n different colors, then obviously f(n) = n * f(n-1) which results in the n! time complexity overall.

  • 0

    @htrinh yes you are right. I have updated it. Thanks

  • 0

    Lets say if there was a follow up question to print the boxes in the order you pick them to achieve maximum score, how can we do that? Eg. if the input was [1,2,1], it should print: 2, 1, 1.

  • 0

    Approach-2 has been updated. Thanks.

  • 0

    I don't feel that O(n^3) time can be achieved.

    For input like 12121212121..... each [l,r] pairing can have every k <=(r-l+1)/2 and for each of those subproblems they would still iterate over (r-l+1)/2 or so i which match r.

    Are you sure O(n^3) is possible?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.