Is Minimum Capacity Box easy or hard?

Minimum Capacity Box is considered an Easy problem. The core observation is that the required capacity equals the largest item size, which can be found with a simple O(n) array traversal.

Minimum Capacity Box Python/Java solution

Both Python and Java implementations follow the same logic: iterate through the array and track the largest element. Python typically uses a loop or the built-in max function, while Java uses a loop with a variable that updates whenever a larger value appears.

How to solve Minimum Capacity Box in O(n)?

Iterate through the array and maintain a variable storing the maximum value seen so far. For each element, compare it with the current maximum and update if it is larger. After processing all elements, the maximum value represents the minimum box capacity required.

What is the best approach for Minimum Capacity Box?

The best approach is a single pass scan that finds the maximum element in the array. The box must accommodate the largest item, so the minimum required capacity equals the maximum value in the array. This solution runs in O(n) time and uses O(1) extra space.

Is Minimum Capacity Box asked at Google/Amazon/Meta?

Problems that involve scanning an array to determine limits or capacity constraints are common in interviews at companies like Amazon and Google. While this exact problem may vary in wording, identifying maximum values in O(n) time is a frequently tested pattern.

What data structure is used in Minimum Capacity Box?

The problem uses a simple array as the input data structure. The algorithm only requires sequential traversal and a variable to track the maximum value, so no additional data structures like stacks, heaps, or hash maps are necessary.

What is the time complexity of Minimum Capacity Box?

The optimal solution runs in O(n) time because the array is traversed once to compute the maximum element. Space complexity is O(1) since only a single variable is used to track the current maximum capacity.

Description Hints 3 Solution Video 30:49

3861. Minimum Capacity Box

Easy72.8% acceptance

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.

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

Topics

Array

Hints open one at a time

Hint 1

Iterate to find the minimum capacity >= itemSize, updating index only on strictly smaller finds.

Hint 2

Handle ties by keeping the earliest index.

Hint 3

Return -1 if no valid box exists.

30:49

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minimumIndex(self, capacity: list[int], itemSize: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,5,3,7]
3

Input

[3,5,4,3]
2

Input

[4]
5

Your code is saved on this device.Solution