Minimum Capacity Box

Difficulty: Easy | Acceptance: 72.60% | Paid: No Topics: Array

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.

• Examples
• Constraints
• Linear Scan
• Two Pass

Examples

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 <= 100
- 1 <= capacity[i] <= 100
- 1 <= itemSize <= 100

Linear Scan

Intuition

Iterate through the array once, tracking the minimum valid capacity seen so far and its index. A box is valid if its capacity is at least itemSize. Because we scan left to right, the first occurrence of any capacity value is naturally the smallest index.

Steps

• Initialize minCap to infinity and result to -1.
• For each index i, if capacity[i] >= itemSize and capacity[i] < minCap, update minCap and result.
• Return result.

class Solution:
    def minimumBox(self, capacity: List[int], itemSize: int) -> int:
        result = -1
        min_cap = float('inf')
        for i, c in enumerate(capacity):
            if c >= itemSize and c < min_cap:
                min_cap = c
                result = i
        return result

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Single pass with constant extra space. The strict < comparison ensures ties resolve to the leftmost index automatically.

Two Pass

Intuition

Separate the problem into two clear steps: first find the minimum capacity among all valid boxes, then find the first index that has exactly that capacity.

Steps

• Pass 1: scan all boxes and track the minimum capacity value that is >= itemSize.
• If no valid capacity found, return -1.
• Pass 2: scan again and return the first index whose capacity equals the minimum found.

class Solution:
    def minimumBox(self, capacity: List[int], itemSize: int) -> int:
        min_cap = min((c for c in capacity if c >= itemSize), default=None)
        if min_cap is None:
            return -1
        return capacity.index(min_cap)

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Two passes over the array, still linear time and constant space. Slightly more readable by separating the two concerns.