Remove Boxes

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
AppleMeeshoFlipkart limited

Problem statement

You are given several boxes with different colours represented by different positive numbers. For moving the boxes you can remove them in multiple iterations until there are no boxes left. Now, every 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 for removing them.

Your task for the problem is to find and return the maximum points you can get by removing those boxes.

For Example: 
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] (Remove 3 boxes with number 2, 3*3=9 points) 
----> [1, 3, 3, 3, 1] (Remove one box with number 4, 1*1=1 points) 
----> [1, 1] (Remove 3 boxes with number 3, 3*3=9 points) 
----> [] (2*2=4 points)
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ denoting the number of test cases that would be there.

The first line of each test case contains a single integer ‘N’ denoting the number of boxes that would be given.

And the next line contains ‘N’ space-separated integers which are the colors of the boxes represented as integers.
Output Format : 
For each test case, print the maximum points that could be collected by removing the boxes of the same color from the list.

The output of each test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= boxes.length <= 50
1 <= boxes[i] <= 100

Time Limit: 1 sec
Sample Input 1 :
2
7
1 2 3 3 2 1 1
9
1 3 2 2 2 3 4 3 1
Sample Output 1:
17
23
Explanation Of Sample Input 1:
Test Case 1:
[1, 2, 3, 3, 2, 1, 1] 
Remove 33 ----> [1, 2, 2, 1, 1] (2 * 2 = 4 points) 
Remove 22 ----> [1, 1, 1] (2 * 2 = 4 points) 
Remove 111 ----> [] (3 * 3 = 9 points) 
Thus, total points are 17.

Test Case 2:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
Remove 222 ----> [1, 3, 3, 4, 3, 1] (3 * 3 = 9 points) 
Remove 4 ----> [1, 3, 3, 3, 1] (1 * 1 = 1 points) 
Remove 333 ----> [1, 1] (3 * 3 = 9 points) 
Remove 22 ----> [] (2 * 2 = 4 points)
Thus, total points are 23.
Sample Input 2 :
1
3
1 1 1
Sample Output 2 :
9
Explanation Of Sample Input 2:
Test Case 1:
[1, 1, 1]
Remove 111 ----> [] (3 * 3 = 9 points) 
Thus, total points are 9.
Hint

Try to recursively maximize the points by checking which box removals are the most profitable out of all the different possible removals.

Approaches (3)
Recursion Approach

Approach: The idea here is to store the repeated set of sub solutions for the problem. Then return the solution you already have calculated the value for recursively building the lookup table. 

 

The algorithm will be:

  1. The first conditions would be to handle the base cases which are when the list of boxes either have no boxes when we return a profit to be 0 while if there is only one box then a max profit of 1 is returned by the function.
  2. Now, while we iterate through the list of boxes keeping track of the starting index ‘START_INDEX’ and the ending index ‘END_INDEX’ of the continuous set of boxes that we are able to find.
  3. Initialise a ‘MAX_PROFIT’ variable with 0 and for those set of boxes, we check if there is a continuous set of boxes having the same colour in the following manner:-
    • Store the box at the ‘START_INDEX’ in a variable ‘PREV_BOX’ and also initialise a ‘BOX_COUNT’ with a value of 0.
    • Now until the ‘END_INDEX’ of the boxes is less than the length of the boxes in the list and the colour of the boxes are continuously the same as the colour of ‘PREV_BOX’ we iterate through the boxes and keep incrementing the value of ‘END_INDEX’ and ‘BOX_COUNT’.
    • If the ‘END_INDEX’ becomes greater than or equal to the length of the boxes we try to maximise the profit by
      1. ‘MAX_PROFIT’ = max(‘MAX_PROFIT’, (‘BOX_COUNT’ * ‘BOX_COUNT’))
    • Otherwise, the profit would be as follows:
      1. ‘MAX_PROFIT’ = max(‘MAX_PROFIT’, maximizePointsByRemovingBoxes(boxes[0:’START_INDEX’] + boxes[‘END_INDEX’:’length_of_boxes’]) + (‘BOX_COUNT’ * ‘BOX_COUNT’))
    • At the end of each iteration, update the ‘START_INDEX’ as the ‘END_INDEX’
  4. We finally return the ‘MAX_PROFIT’.
Time Complexity

O(2 ^ N), where ‘N’ denotes the number of boxes given in the problem.

 

Since we are splitting the problem into subproblems of smaller size in each iteration recursively therefore, the time complexity will be O(2 ^ N).

Space Complexity

O(N), where ‘N’ denotes the number of boxes given in the problem.

 

Since we are making as many recursive calls as the height of the tree and the tree is at most n height. That is why the space complexity is O(N)

Code Solution
(100% EXP penalty)
Remove Boxes
Full screen
Console