Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Apple Redistribution into Boxes

Problem Statement

You are given an array apple of size n, where the apple[i] represents the number of apples in i<sup>th</sup> pack. You are also given an array capacity of size m, where capacity[j] is a number of apples that can be stored in the j<sup>th</sup> box.

Return the minimum number of boxes you need to use to put these all n packs of apples into boxes.

Note: You are allowed to distribute apples from the same pack into different boxes.

Examples

Example 1:

  • Input: apple = [2, 3, 1], capacity = [4, 2, 5, 1]
  • Expected Output: 2

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jimmy

· 2 years ago

  1. Why are we sorting the capacities in ascending order and then iterating from the end? Why don't we just sort the capacities in descending order and iterate from the start? Seems simpler and less convoluted.
  2. Why is the space complexity O(n)? Shouldn't the space be O(m) since we are sorting the capacity (and not the apple) array?
Show 1 reply
Debasis B

Debasis B

· 2 years ago

Here we assume there's always enough capacity for all the apples. Shouldn't this be mentioned in the question? If the total number of apples is > total capacity we get an incorrect answer.

Raj Shekar

Raj Shekar

· a year ago

  1. Initially its mentioned that capacity array will be sorted in descending order. Please check below:

        **We will start by sorting the `capacity` array in descending order so we can always access the largest box first.** 

  2. But later it has been sorted in ascending in order and mentioned accordingly. Please check below:

         **Step 1: Sort the `boxCapacities` array in ascending order to strategically use the largest boxes last.**

  3. Again in explanation part use of priority queue has been mentioned, but in code solution it has not been used.

The apples from each pack will be allocated starting from the box with the highest capacity, using a priority queue to manage and update the available space in the boxes quickly.

Show 1 reply