Skip to main content
Talentd

Minimum Capacity Box - Solution & Explanation

EasyArray6 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solution

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.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting the ArrayO(n log n)O(1)When the array is already being sorted for other operations
Single Pass Maximum ScanO(n)O(1)General case; fastest way to determine required capacity

Video Solution

Leetcode Weekly Contest 492 || Q1, Q2, Q3, Q4 || Recursion, String, Sorting, Prefix Sum || Watch 2X🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 1,136 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Capacity Box with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays