Amazon OA: Minimum Boxes to Unload
The supply chain manager at one of Amazon’s warehouses is shipping the last container of the day. All n boxes have been loaded into the truck, with their sizes represented in the array boxes.
The truck may not have enough capacity to store all the boxes, so some of the boxes may have to be unloaded. The remaining boxes must satisfy the condition:
max(boxes) <= capacity * min(boxes)Given the array boxes and capacity, find the minimum number of boxes that need to be unloaded.
Example
Given n = 4, boxes = [1, 4, 3, 2], and capacity = 2.
Unloading box 0 with size 1 leaves [4, 3, 2].
Now max([4, 3, 2]) = 4 and capacity * min([4, 3, 2]) = 2 * 2 = 4.
This satisfies the required condition, so the answer is 1.
Function Description
Complete the function removeBoxes in the editor below.
public static int removeBoxes(List<Integer> boxes, int capacity)Returns
An integer denoting the minimum number of boxes that need to be unloaded.
Sample Input For Custom Testing
6
4
5
3
8
3
7
2Sample Output
2Explanation
Remove boxes of size 8 and 7. Then the remaining boxes are [4, 5, 3, 3], where max = 5 and min = 3, and 5 <= 3 * 2.
Alternatively, remove the two boxes of size 3. Then the remaining boxes are [4, 5, 8, 7], where max = 8 and min = 4, and 8 <= 4 * 2.
The key idea is to keep the remaining boxes within a value range where max(boxes) <= capacity * min(boxes). After sorting the array, this becomes a longest valid subarray problem: for each possible minimum value at the left side of the window, expand the right side as far as possible while the condition still holds. The minimum number of boxes to unload is then the total size minus the largest valid window length. A sorted two-pointer scan is the natural and efficient approach.
