LeetCode 3861 - Minimum Capacity Box

LeetCode Problem 3861

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem presents a straightforward search scenario. You are given an array capacity where each element represents the storage capacity of a box. You are also given an integer itemSize, representing the size of an item you want to store. The task is to find the index of the box that has the smallest capacity that is still large enough to hold the item. If multiple boxes satisfy this condition, you return the first (smallest) index among them. If no box can hold the item, you return -1.

The input is guaranteed to be small (1 <= capacity.length <= 100 and values in [1, 100]), so we can afford to scan the entire array without performance issues. Important edge cases include situations where all boxes are too small, where multiple boxes have the same minimum sufficient capacity, and where the array has only one element.

Approaches

The simplest approach is a brute-force linear scan. You iterate through all boxes, tracking the minimum capacity that can hold the item, along with its index. Because the array length is at most 100, this approach is efficient enough and straightforward to implement.

The optimal solution is essentially the same as brute force for this input size, but with careful handling of tracking both the minimum capacity and the smallest index. The key observation is that there is no need for sorting or additional data structures because the array is small and we need the original index. By maintaining a running min_capacity and min_index, we can find the answer in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan array, track minimum sufficient capacity and index
Optimal	O(n)	O(1)	Same as brute force; single-pass linear scan with running minimum

Algorithm Walkthrough

1. Initialize min_capacity to a value larger than the maximum possible capacity (e.g., 101) and min_index to -1.
2. Iterate through each box in the capacity array by index.
3. For each box, check if its capacity is greater than or equal to itemSize.
4. If it can hold the item, compare it with min_capacity.
5. If the current box's capacity is smaller than min_capacity, update min_capacity and set min_index to the current index.
6. Continue until all boxes are processed.
7. Return min_index. If no box was sufficient, it remains -1.

Why it works: By maintaining a running minimum of capacities that can store the item, we guarantee that at the end of the loop, min_index points to the box with the smallest capacity capable of holding the item. This also ensures that if multiple boxes have the same minimum capacity, the first index is returned because we only update min_index when we find a strictly smaller capacity.

Python Solution

class Solution:
    def minimumIndex(self, capacity: list[int], itemSize: int) -> int:
        min_capacity = 101
        min_index = -1
        for i, c in enumerate(capacity):
            if c >= itemSize:
                if c < min_capacity:
                    min_capacity = c
                    min_index = i
        return min_index

In this implementation, min_capacity is initialized to 101 because no box can exceed 100 by constraints. We iterate with enumerate to access both index and value. If the box can store the item and is smaller than the current min_capacity, we update both the capacity and index. Finally, we return the resulting min_index.

Go Solution

func minimumIndex(capacity []int, itemSize int) int {
    minCapacity := 101
    minIndex := -1
    for i, c := range capacity {
        if c >= itemSize {
            if c < minCapacity {
                minCapacity = c
                minIndex = i
            }
        }
    }
    return minIndex
}

The Go version mirrors the Python logic. We declare minCapacity and minIndex and iterate over the slice using range to get both index and value. Updates happen under the same condition checks. Go handles slices and integer values natively, so there are no additional considerations for empty input since the loop will simply not execute.

Worked Examples

Example 1: capacity = [1,5,3,7], itemSize = 3

Index	Capacity	Can Store?	min_capacity	min_index
0	1	No	101	-1
1	5	Yes	5	1
2	3	Yes	3	2
3	7	Yes	3	2

Output: 2

Example 2: capacity = [3,5,4,3], itemSize = 2

Index	Capacity	Can Store?	min_capacity	min_index
0	3	Yes	3	0
1	5	Yes	3	0
2	4	Yes	3	0
3	3	Yes	3	0

Output: 0

Example 3: capacity = [4], itemSize = 5

Index	Capacity	Can Store?	min_capacity	min_index
0	4	No	101	-1

Output: -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan each box exactly once
Space	O(1)	Only two extra variables are used

Because the array length is at most 100, this is extremely efficient and does not require additional memory.

Test Cases

# Provided examples
assert Solution().minimumIndex([1,5,3,7], 3) == 2  # minimum capacity that can store item
assert Solution().minimumIndex([3,5,4,3], 2) == 0  # multiple boxes same capacity, return smallest index
assert Solution().minimumIndex([4], 5) == -1        # no box can store item

# Edge cases
assert Solution().minimumIndex([100], 100) == 0     # single box fits exactly
assert Solution().minimumIndex([100], 101) == -1    # single box too small
assert Solution().minimumIndex([2,2,2,2], 2) == 0   # all equal, multiple boxes fit
assert Solution().minimumIndex([1,2,3,4,5], 5) == 4 # last box fits
assert Solution().minimumIndex([5,4,3,2,1], 3) == 2 # middle box minimum

Test	Why
[1,5,3,7], 3	Normal case with multiple sufficient boxes
[3,5,4,3], 2	Multiple boxes same min capacity, check smallest index
[4], 5	Single box too small
[100], 100	Single box exactly fits
[100], 101	Single box too small, should return -1
[2,2,2,2], 2	All boxes same capacity, should pick first index
[1,2,3,4,5], 5	Minimum fits last box
[5,4,3,2,1], 3	Minimum fits middle box

Edge Cases

One important edge case is when no box can store the item, as in [4] with itemSize = 5. If we forget to initialize min_index to -1, the algorithm might return 0 incorrectly. Another edge case is when multiple boxes have the same minimum sufficient capacity, such as [3,5,4,3] with itemSize = 2. We need to ensure we return the first index, which is handled by updating min_index only when a strictly smaller capacity is found. Finally, the single-element array is an edge case that could break naive loops if not handled properly; our approach works because the loop iterates correctly regardless of array size.