Crushing Heavy Boxes

Question

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 strictly greater weight than the box on the top of the stack. If a box is crushed, it is permanently removed from the stack, and the incoming box is then compared with the new top of the stack. This crushing process cascades until the incoming box cannot crush the top box (either because the stack is empty, the top box has a different color, or the top box has a weight greater than or equal to the incoming box). At that point, the incoming box is placed on top of the stack. Return an array of the weights of the boxes remaining in the stack after processing all input boxes in the given order.

DSAMaster · Accepted Answer

To optimally solve the Crushing Heavy Boxes problem involving Stack, it is important to analyze constraints. Time Complexity: O(N), Space Complexity: O(N). 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.

Crushing Heavy Boxes Solution

Problem Statement

Examples

Constraints

Run, Test & Submit Code

Tested Solutions

Related Problems