Crushing Heavy Boxes ā Problem Statement & Solution Guide
Problem Description
You are managing a warehouse conveyor belt where boxes are stacked sequentially. Each box is represented by an array of two integers [weight, color]. You process the boxes from left to right, placing them onto a single vertical stack. When a new box is placed on the stack, it may crush the box directly below it if both of the following conditions are met: 1. They have the same color. 2. The incoming box has a greater weight than the box directly below it. The output should be a list of the weights of the boxes in the final stack.
Examples
Input
[[1, 1], [2, 1], [3, 1], [4, 2]]
Output
[3, 2, 4]
Explanation: Step-by-step: 1. We start with an empty stack. 2. We process the boxes from left to right. 3. The box [1, 1] is placed on the stack. 4. The box [2, 1] is placed on top of the box [1, 1] because they have the same color and weight. 5. The box [3, 1] is placed on top of the box [2, 1] because they have the same color and weight. 6. The box [4, 2] is placed on top of the box [3, 1] because they have different colors.
Input
[[6, 1], [3, 1], [2, 1]]
Output
[6, 3, 2]
Explanation: Step-by-step: 1. We start with an empty stack. 2. We process the boxes from left to right. 3. The box [6, 1] is placed on the stack. 4. The box [3, 1] is placed on top of the box [6, 1] because they have the same color and weight. 5. The box [2, 1] is placed on top of the box [3, 1] because they have the same color and weight.
Constraints
- 1 <= boxes.length <= 10^5
- boxes[i].length == 2
- 1 <= boxes[i][0], boxes[i][1] <= 10^9
Optimal Approach & Strategy
The optimal approach uses a stack to process each box in a single pass. For each box, we run a while loop to check if the stack top shares the same color and has a strictly lower weight. If so, we pop the top element and repeat the check. Once the condition fails or the stack becomes empty, we push the current box. This achieves O(n) complexity because each box is pushed and popped at most once.
Brute Force Approach
A naive approach would maintain the sequence of boxes in an array. For each new box, we append it to the end and then scan backwards to find if any adjacent elements of the same color can be crushed, shifting the elements to fill the gaps. This results in an O(nĀ²) time complexity due to the repeated scanning and shifting of elements.
Verified Code Solutions
class Solution {
public int[] crushBoxes(int[][] boxes) {
Stack<int[]> stack = new Stack<>();
for (int[] box : boxes) {
while (!stack.isEmpty() && stack.peek()[0] < box[0] && stack.peek()[1] == box[1]) {
stack.pop();
}
stack.push(box);
}
int[] result = new int[stack.size()];
for (int i = 0; i < stack.size(); i++) {
result[i] = stack.get(i)[0];
}
return result;
}
}def crush_boxes(boxes):
stack = []
for box in boxes:
while stack and stack[-1][0] < box[0] and stack[-1][1] == box[1]:
stack.pop()
stack.append(box)
return [box[0] for box in stack]Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.