Skip to main content
Talentd

Apple Redistribution into Boxes - Solution & Explanation

EasyArrayGreedySorting13 min readAsked at: Apple, Google, Bloomberg
Practice this problem

Problem Statement

You are given an array apple of size n and an array capacity of size m.

There are n packs where the ith pack contains apple[i] apples. There are m boxes as well, and the ith box has a capacity of capacity[i] apples.

Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes.

Note that, apples from the same pack can be distributed into different boxes.

 

Example 1:

Input: apple = [1,3,2], capacity = [4,3,1,5,2]
Output: 2
Explanation: We will use boxes with capacities 4 and 5.
It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.

Example 2:

Input: apple = [5,5,5], capacity = [2,4,2,7]
Output: 4
Explanation: We will need to use all the boxes.

 

Constraints:

  • 1 <= n == apple.length <= 50
  • 1 <= m == capacity.length <= 50
  • 1 <= apple[i], capacity[i] <= 50
  • The input is generated such that it's possible to redistribute packs of apples into boxes.

Approach Overview

Problem Overview: You are given two arrays: apple representing apples in each pack and capacity representing the capacity of available boxes. The goal is to redistribute all apples into the minimum number of boxes without exceeding any box’s capacity.

Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)

This problem reduces to a simple observation: the total number of apples matters, not which pack they came from. First compute the total apples using a single pass through the apple array. Then sort the capacity array in descending order and keep picking the largest box capacities until their combined capacity can hold all apples. The greedy choice works because using the largest boxes first minimizes the number of boxes required. Sorting dominates the runtime at O(m log m) where m is the number of boxes, while the accumulation step is linear.

The approach relies on concepts commonly used in Greedy strategies: always take the locally optimal choice (largest capacity) to reach a global optimum. Sorting the capacities is what makes the greedy selection straightforward, connecting the solution to patterns from Sorting problems.

Approach 2: Priority Queue (Heap) Selection (O(m log m) time, O(m) space)

Instead of sorting all capacities upfront, push every box capacity into a priority queue and repeatedly extract the largest capacity box until the total capacity covers all apples. Each extraction represents selecting the next best box. If a max‑heap is not directly available, you can simulate it by inserting negative values into a min‑heap. Every heap insertion and removal costs O(log m), resulting in O(m log m) overall time.

This method is useful when capacities arrive dynamically or when you only need the top few elements rather than a fully sorted array. The data structure involved is a Priority Queue, which efficiently retrieves the largest remaining capacity each step.

Recommended for interviews: The greedy sorting approach is what most interviewers expect. It shows you recognize that the order of apple packs is irrelevant and that minimizing boxes simply means selecting the largest capacities first. The heap version demonstrates familiarity with priority queues but is usually unnecessary since sorting is simpler and slightly more memory efficient. Showing the greedy reasoning clearly is the key signal of strong problem‑solving skills.

Approach 1: Greedy Approach for Minimizing Box Usage

This approach suggests sorting the box capacities in descending order and continuously filling the boxes until all apple packs are distributed. The greedy nature ensures we utilize boxes with maximum capacity first, minimizing the total number of boxes used.

This C function uses a greedy algorithm. First, it calculates the total number of apples, then sorts the capacity array in descending order. It iteratively subtracts the largest available box capacity from the total apple count, until all apples are redistributed. The number of iterations gives the minimum number of boxes used.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m log m) due to sorting, and O(m) for iterating over the boxes. Total is O(m log m).
Space Complexity: O(1), as the sorting is done in place.

Try this approach in the editor →

Approach 2: Use of Priority Queue (Min-Heap Structure)

This approach is alternative to the greedy method, which leverages a priority queue (min-heap) to manage capacities and ensures that the smallest required boxes are filled first. This can be useful in scenarios where random access to the smallest element is necessary. Although it may not be optimal for the current arrangement, it provides a perspective on alternative sorting.

In C++, the standard library provides a priority queue, which can be used for managing smallest elements efficiently. The code leverages this to consistently use the smallest box capacity still needed and adjusts the total until all apples are distributed.

Code

C++Python

C++

Python

Complexity

Time Complexity: O(m log m) for heap management operations.
Space Complexity: O(m) since space is required for the priority queue.

Try this approach in the editor →

Approach 3: Greedy + Sorting

To minimize the number of boxes needed, we should prioritize using boxes with larger capacities. Therefore, we can sort the boxes in descending order of capacity, and then use the boxes one by one until all the apples are packed. We return the number of boxes used at this point.

The time complexity is O(m times log m + n) and the space complexity is O(log m), where m and n are the lengths of the arrays capacity and apple respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach for Minimizing Box Usage

Time Complexity: O(m log m) due to sorting, and O(m) for iterating over the boxes. Total is O(m log m).
Space Complexity: O(1), as the sorting is done in place.

Use of Priority Queue (Min-Heap Structure)

Time Complexity: O(m log m) for heap management operations.
Space Complexity: O(m) since space is required for the priority queue.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(m log m)O(1)Best general solution. Simple implementation and minimal memory usage.
Priority Queue (Heap)O(m log m)O(m)Useful when capacities arrive dynamically or when repeatedly selecting the largest element.

Video Solution

Apple Redistribution into Boxes | Simple Explanation | Homework Inside | Leetcode 3074 | MIK • codestorywithMIK • 3,412 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Apple Redistribution into Boxes easy or hard?
Apple Redistribution into Boxes is classified as an Easy problem on LeetCode with a high acceptance rate around 78%. The challenge mainly tests whether you recognize the greedy insight that selecting the largest box capacities first minimizes the number of boxes required.
Apple Redistribution into Boxes Python/Java solution
Most implementations follow the same steps: sum all apples, sort the capacity array in descending order, and accumulate capacities until the total meets or exceeds the apple count. This logic translates directly into Python, Java, C++, JavaScript, and other languages with built-in sorting utilities.
How to solve Apple Redistribution into Boxes in O(n)?
A true O(n) solution generally requires constraints such as bounded capacities that allow counting sort or bucket techniques. In the general case with arbitrary values, the optimal practical solution sorts the capacities and runs in O(m log m) time. The greedy selection of the largest capacities ensures the minimum number of boxes.
What is the best approach for Apple Redistribution into Boxes?
The most efficient approach is a greedy strategy. First calculate the total number of apples, then sort the box capacities in descending order and keep selecting the largest boxes until their combined capacity holds all apples. Sorting costs O(m log m) time where m is the number of boxes, and the rest of the process is linear.
Is Apple Redistribution into Boxes asked at Google/Amazon/Meta?
Problems using greedy selection and capacity allocation patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the underlying technique of sorting resources and selecting the largest first is a common interview pattern.
What data structure is used in Apple Redistribution into Boxes?
The primary data structure is an array combined with sorting for the greedy solution. An alternative implementation uses a priority queue (max-heap) to repeatedly extract the box with the largest remaining capacity.
What is the time complexity of Apple Redistribution into Boxes?
The optimal solution runs in O(m log m) time due to sorting the box capacities. After sorting, you accumulate capacities until they cover the total number of apples, which takes O(m) time. Space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Apple Redistribution into Boxes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays