Watch 5 video solutions for Minimum Capacity Box, a easy level problem involving Array. This walkthrough by Developer Coder has 194 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array capacity, where capacity[i] represents the capacity of the ith box, and an integer itemSize representing the size of an item.
The ith box can store the item if capacity[i] >= itemSize.
Return an integer denoting the index of the box with the minimum capacity that can store the item. If multiple such boxes exist, return the smallest index.
If no box can store the item, return -1.
Example 1:
Input: capacity = [1,5,3,7], itemSize = 3
Output: 2
Explanation:
The box at index 2 has a capacity of 3, which is the minimum capacity that can store the item. Thus, the answer is 2.
Example 2:
Input: capacity = [3,5,4,3], itemSize = 2
Output: 0
Explanation:
The minimum capacity that can store the item is 3, and it appears at indices 0 and 3. Thus, the answer is 0.
Example 3:
Input: capacity = [4], itemSize = 5
Output: -1
Explanation:
No box has enough capacity to store the item, so the answer is -1.
Constraints:
1 <= capacity.length <= 1001 <= capacity[i] <= 1001 <= itemSize <= 100Problem Overview: You’re given an array representing item sizes. The goal is to determine the minimum capacity a single box must have so every item fits inside it. The box must be large enough for the largest item, otherwise that item cannot be stored.
Approach 1: Sorting the Array (O(n log n) time, O(1) extra space)
One straightforward way to determine the required capacity is to sort the array and inspect the largest element. After sorting in ascending order, the last value represents the maximum item size, which directly determines the minimum capacity the box must support. Sorting guarantees the maximum element is placed at the end. This works reliably but performs unnecessary work because the entire array is rearranged just to identify a single value.
This method is useful if the data is already being sorted for another operation. Otherwise, sorting increases the runtime from linear to O(n log n), which is inefficient for a simple maximum lookup.
Approach 2: Single Pass Maximum Scan (O(n) time, O(1) space)
The optimal solution scans the array once and tracks the maximum value encountered so far. Initialize a variable such as maxCapacity with the first element. Iterate through the array and update the variable whenever a larger value appears. By the end of the traversal, this value represents the largest item size in the array.
The key insight is that the minimum valid box capacity must be at least the size of the largest item. Any smaller capacity would fail to store that item. Since finding a maximum only requires a linear scan, the algorithm runs in O(n) time and uses constant O(1) extra space.
This pattern appears frequently in problems involving limits, thresholds, or capacity constraints within an array. Instead of simulating packing or trying multiple capacities, you compute the hard lower bound directly from the data.
Recommended for interviews: Interviewers expect the single pass maximum scan. It demonstrates that you recognize the capacity constraint immediately and avoid unnecessary operations like sorting. Mentioning the sorting approach first shows baseline reasoning, while implementing the O(n) scan highlights strong understanding of array traversal and simple greedy observations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting the Array | O(n log n) | O(1) | When the array is already being sorted for other operations |
| Single Pass Maximum Scan | O(n) | O(1) | General case; fastest way to determine required capacity |