3861. Minimum Capacity Box

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array capacity, where capacity[i] represents the capacity of the i^th box, and an integer itemSize representing the size of an item.

The i^th 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Single-pass linear scan to find the smallest-capacity box meeting the threshold, keeping the earliest match via strict comparison.

Open in Flowchart

Intuition

The core of this problem is to find, among all boxes that can hold the item, the one with the smallest capacity, and if there are ties, the one with the smallest index.

A box is a valid candidate only if its capacity is at least itemSize, i.e., capacity[i] >= itemSize. So the first thing we need to do for each box is check whether it satisfies this condition.

Among all the valid candidates, we want the one with the minimum capacity. This naturally suggests keeping track of the "best answer so far" as we scan through the array. We maintain a variable ans that stores the index of the best valid box found up to the current point.

When we encounter a new valid box, we compare its capacity with the capacity of our current best box:

If we have not yet found any valid box (ans == -1), then this box becomes our first candidate.
Otherwise, we only update ans if the current box's capacity is strictly smaller than capacity[ans].

The reason we use a strict comparison (x < capacity[ans]) is important for the tie-breaking rule. If two boxes have the same capacity, we want to keep the one with the smaller index. Since we scan from left to right, the earlier index is already stored in ans, and using a strict comparison ensures we do not overwrite it with a later box of equal capacity.

By going through the entire array just once and always remembering the best valid box so far, we end up with the smallest-capacity box (with the smallest index in case of ties) when the loop finishes. If no box ever qualified, ans remains -1, which is exactly the value we should return.

Solution Approach

Solution 1: Single Pass

We initialize a variable ans to represent the index of the box with the smallest capacity that can hold the item, with an initial value of -1. We iterate over the array capacity, and for each box, if its capacity is greater than or equal to itemSize, it can hold the item. At this point, we check whether it is the smallest-capacity box found so far; if so, we update ans. Finally, we return ans.

Let's break the implementation down step by step:

Initialization: We set ans = -1. This serves two purposes at once — it acts as our "no valid box found yet" marker, and it is also the value we return if no box can ever hold the item.
Iterate with index and value: We use enumerate(capacity) to loop through the array, getting both the index i and the capacity value x of each box in a single pass.
Check the condition: For each box, we evaluate the combined condition x >= itemSize and (ans == -1 or x < capacity[ans]):
- x >= itemSize ensures the box is a valid candidate that can hold the item.
- ans == -1 handles the case where this is the first valid box we have seen, so we accept it directly.
- x < capacity[ans] ensures we only replace the current best when we find a box with a strictly smaller capacity. The strict comparison preserves the smallest-index rule when capacities are equal, since we scan from left to right.
Update the answer: When the condition holds, we update ans = i to record the index of the new best box.
Return the result: After the loop completes, ans holds the index of the smallest-capacity box that can store the item, or -1 if no such box exists.

This approach uses a simple single pass (linear scan) pattern with only a constant amount of extra space.

Time complexity: O(n), where n is the length of the array capacity, since we examine each element exactly once.
Space complexity: O(1), as we only use the single variable ans regardless of the input size.

Example Walkthrough

Let's trace through the solution with a small example:

capacity = [5, 3, 8, 3, 6]
itemSize = 4

We want to find the index of the box with the minimum capacity that can still hold the item (capacity >= 4), breaking ties by choosing the smallest index.

We start with ans = -1 (no valid box found yet).

Iteration 1 — i = 0, x = 5:

Is x >= itemSize? 5 >= 4 → ✅ valid candidate.
Is ans == -1? Yes, this is our first valid box.
Update ans = 0.
Best so far: index 0 with capacity 5.

Iteration 2 — i = 1, x = 3:

Is x >= itemSize? 3 >= 4 → ❌ too small to hold the item.
Skip. ans stays 0.

Iteration 3 — i = 2, x = 8:

Is x >= itemSize? 8 >= 4 → ✅ valid candidate.
Is ans == -1? No (ans = 0).
Is x < capacity[ans]? 8 < 5 → ❌ not smaller than current best.
Skip. ans stays 0.

Iteration 4 — i = 3, x = 3:

Is x >= itemSize? 3 >= 4 → ❌ too small.
Skip. ans stays 0.

Iteration 5 — i = 4, x = 6:

Is x >= itemSize? 6 >= 4 → ✅ valid candidate.
Is ans == -1? No (ans = 0).
Is x < capacity[ans]? 6 < 5 → ❌ not smaller than current best.
Skip. ans stays 0.

Result: The loop finishes with ans = 0. The box at index 0 (capacity 5) is the smallest-capacity box that can hold an item of size 4, so we return 0.

Why the strict comparison matters (a tie-break note): Suppose instead capacity = [5, 5, 8] and itemSize = 4. At i = 0, ans becomes 0 (capacity 5). At i = 1, the box also has capacity 5, but 5 < 5 is false, so we do not overwrite ans. This preserves the smallest index 0 among the tied capacities — exactly the behavior the strict < comparison guarantees.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minimumIndex(self, capacity: List[int], item_size: int) -> int:
6        # Index of the best (smallest sufficient) capacity found so far; -1 means none yet
7        best_index = -1
8
9        # Iterate over every container with its index
10        for index, current_capacity in enumerate(capacity):
11            # The container must be able to hold the item (capacity >= item_size)
12            # and it should be smaller than the current best candidate (tightest fit)
13            if current_capacity >= item_size and (
14                best_index == -1 or current_capacity < capacity[best_index]
15            ):
16                best_index = index
17
18        # Return the index of the smallest container that still fits the item,
19        # or -1 if no container is large enough
20        return best_index
21

1class Solution {
2    /**
3     * Finds the index of the box with the smallest capacity that can still
4     * hold an item of the given size.
5     *
6     * @param capacity an array where each element represents a box's capacity
7     * @param itemSize the size of the item to be placed
8     * @return the index of the most suitable box, or -1 if none qualifies
9     */
10    public int minimumIndex(int[] capacity, int itemSize) {
11        // Index of the best candidate found so far; -1 means none yet.
12        int ans = -1;
13
14        // Iterate over every box.
15        for (int i = 0; i < capacity.length; ++i) {
16            int currentCapacity = capacity[i];
17
18            // The box qualifies if it can hold the item and is either the
19            // first valid box found or smaller than the current best.
20            if (currentCapacity >= itemSize
21                    && (ans == -1 || currentCapacity < capacity[ans])) {
22                ans = i;
23            }
24        }
25
26        // Return the index of the smallest qualifying box, or -1 if none.
27        return ans;
28    }
29}
30

1class Solution {
2public:
3    int minimumIndex(vector<int>& capacity, int itemSize) {
4        // Index of the best (minimum-capacity) container found so far; -1 means none yet
5        int bestIndex = -1;
6
7        // Iterate over every container
8        for (int i = 0; i < static_cast<int>(capacity.size()); ++i) {
9            int currentCapacity = capacity[i];
10
11            // The container must be able to hold the item (capacity >= itemSize),
12            // and it should be either the first valid one found,
13            // or have a strictly smaller capacity than the current best.
14            if (currentCapacity >= itemSize &&
15                (bestIndex == -1 || currentCapacity < capacity[bestIndex])) {
16                bestIndex = i;
17            }
18        }
19
20        // Return the index of the container with the minimum sufficient capacity,
21        // or -1 if no container can hold the item.
22        return bestIndex;
23    }
24};
25

1/**
2 * Finds the index of the bin with the smallest capacity that can still
3 * accommodate an item of the given size.
4 *
5 * @param capacity - An array where each element represents the capacity of a bin.
6 * @param itemSize - The size of the item that needs to be placed.
7 * @returns The index of the best-fitting bin, or -1 if no bin can hold the item.
8 */
9function minimumIndex(capacity: number[], itemSize: number): number {
10    // Index of the best candidate bin found so far; -1 means none found yet.
11    let bestIndex = -1;
12
13    // Iterate over every bin to evaluate whether it can hold the item.
14    for (let i = 0; i < capacity.length; ++i) {
15        const currentCapacity = capacity[i];
16
17        // The bin is valid only if it can fit the item, and it must be
18        // strictly smaller than the current best (to ensure the tightest fit).
19        if (
20            currentCapacity >= itemSize &&
21            (bestIndex === -1 || currentCapacity < capacity[bestIndex])
22        ) {
23            bestIndex = i;
24        }
25    }
26
27    // Return the index of the smallest sufficient bin, or -1 if none exists.
28    return bestIndex;
29}
30

Time and Space Complexity

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array capacity.

The code uses a single for loop to iterate through each element of capacity exactly once. For each element, it performs constant-time comparisons (x >= itemSize and x < capacity[ans]) and a possible assignment to ans. Therefore, the total time complexity is O(n).

Only a constant amount of extra space is used, namely the variables ans, i, and x. No additional data structures that scale with the input size are created, so the space complexity is O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using `<=` instead of `<` when comparing capacities, breaking the smallest-index tie-break rule

A very common mistake is writing the comparison as current_capacity <= capacity[best_index] instead of current_capacity < capacity[best_index]. When two valid boxes share the same minimum capacity, the problem requires returning the smallest index. Since we scan left to right, the first box with that capacity should win.

If you use <=, the answer keeps getting overwritten by later boxes that have an equal capacity, so you end up returning the largest index among ties instead of the smallest.

Incorrect:

if current_capacity >= item_size and (
    best_index == -1 or current_capacity <= capacity[best_index]  # BUG: <=
):
    best_index = index

For capacity = [5, 3, 3, 7], item_size = 3, this wrongly returns 2 instead of the correct 1.

Correct: Use a strict < so the earliest occurrence of the minimum capacity is preserved:

if current_capacity >= item_size and (
    best_index == -1 or current_capacity < capacity[best_index]
):
    best_index = index

Pitfall 2: Forgetting the "no valid box" case and mishandling the `-1` sentinel

Because best_index is initialized to -1, accessing capacity[best_index] before confirming a valid box has been found would index into capacity[-1] — the last element in Python — silently producing wrong comparisons instead of an error.

Incorrect:

# Evaluating capacity[best_index] first short-circuits incorrectly
if current_capacity >= item_size and current_capacity < capacity[best_index]:
    best_index = index

Here, when best_index == -1, capacity[best_index] reads the last element of the array, corrupting the logic.

Solution: Always guard the indexed access with the best_index == -1 check placed first, relying on short-circuit evaluation so capacity[best_index] is only ever read once a real candidate exists:

if current_capacity >= item_size and (
    best_index == -1 or current_capacity < capacity[best_index]
):
    best_index = index

The or short-circuits: when best_index == -1 is True, Python never evaluates current_capacity < capacity[best_index], so the -1 indexing trap is avoided entirely.

Pitfall 3: Overcomplicating with sorting

Some solutions sort the array (or pairs of value/index) to find the minimum sufficient capacity. This works but raises time complexity from O(n) to O(n log n) and requires extra bookkeeping to recover the original index along with the smallest-index tie-break. The single-pass approach already achieves the goal in O(n) time and O(1) space — sorting is unnecessary here.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know