1705. Maximum Number of Eaten Apples
Problem Description
In this problem, we have an apple tree that grows a certain number of apples every day for n days. Each apple has an expiration period given by the corresponding index in the days array. This means that if the tree grows apples[i] apples on the i-th day, these apples will rot and become inedible after days[i] days. It is also mentioned that on some days, the tree might not grow any apples, which is represented by apples[i] == 0 and days[i] == 0.
You have a strategy where you eat at most one apple per day, and you're looking to maximize the number of apples you can consume. It's important to note that your apple-eating period can extend beyond the n days of apple growth, meaning you can continue eating the apples you've collected after the tree stops producing new ones.
The goal is to determine the maximum number of apples you can eat using the given apples and days arrays.
Intuition
The intuition behind the solution is to simulate the process of eating apples in a way that prioritizes eating the apples that will rot soonest. This helps in maximizing the number of apples eaten and minimizing waste. We can achieve this through the use of a min-heap data structure.
The min-heap will store pairs of values: the expiration date of the apples and the quantity of those apples. By ensuring that the heap is always sorted by the expiration date (the sooner-to-rot apples at the top), we can efficiently determine which apple to eat next.
Our approach follows these steps:
- Process each day from the given arrays, starting from day 0 until the last day when apples can potentially be eaten (
i < n or qis not empty). - For each day, if the tree grows apples on that day (
apples[i]), add these apples along with their expiration date to the min-heap. - After that, clean the heap by removing any apples that have already rotted (
q[0][0] < i). - If the heap is not empty, eat one apple (the one at the top of the heap since it's the next to rot). Decrease the quantity of that type of apple and increment the total count of eaten apples (
ans). - If there are still apples of the same type left and they haven’t expired yet, put them back into the min-heap with the updated quantity.
- Repeat the above steps for each day, moving forward one day at a time (
i += 1). - Continue even after day
nuntil all the apples that we have are either eaten or rotten.
Using a heap is key here because it allows us to efficiently access the apples that will rot first (heap's root), eat them to prevent waste, and keep the remaining collection of apples well-organized for the upcoming days.
Learn more about Greedy and Heap (Priority Queue) patterns.
Which technique can we use to find the middle of a linked list?
Solution Approach
The solution approach for this problem involves the use of a min-heap data structure, which in Python can be implemented using the heapq library. A min-heap helps us keep track of the apples with the earliest expiration date on top. Let's walk through the key steps in the implementation:
-
We start by initializing a heap
qand settingi = 0andans = 0. The variableitracks the current day, andansis used to count the number of apples eaten. -
We enter a
whileloop that continues as long asi < n(we're within the tree's apple-producing period) or we have apples in our heapq. -
Inside the loop, if it's a productive day (
apples[i] > 0), we add the apples and their expiration day(i + days[i] - 1)as a tuple to the heap. We useheappushfrom theheapqlibrary to maintain the heap invariant (smallest expiration date on top). -
After potentially adding new apples to the heap, we remove any apples that have already rotted. We do this by looping while the heap is not empty and the expiration date of the apples at the top of the heap is less than the current day
q[0][0] < i. If the condition is met, we useheappopto remove the top element from the heap. -
If there are any apples left in the heap (i.e., there are still unrotten apples), we eat one. Since we can only eat one apple a day, we remove the top element from the heap, decrease the apple count by one, and increase the
ansvariable to reflect the eaten apple. -
If there are remaining apples of the type we just ate (their count is now
v - 1) and they have not expired (t > i), we push them back onto the heap with the updated count. -
We increment
ito move to the next day and repeat the process until the heap is empty or we've simulated all days within the apple growth periodn.
This solution approach ensures we are always eating the apple that is closest to rotting, thus maximizing the number of apples we can consume before they go bad.
Remember, the use of a heap is due to its efficient ability to always give us the smallest element, which in this case is the soonest expiration date. The heap's property of log-complexity for insertion and removal operations enables us to manage our collection of apples as they grow and rot throughout the simulated days effectively.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
Example Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following arrays for apples and days:
apples = [1, 2, 3, 0, 0]
days = [3, 2, 1, 0, 0]
This tells us that on day 0 we have 1 apple that expires after 3 days, on day 1 we have 2 apples that expire after 2 days, and on day 2 we have 3 apples that expire after 1 day.
Initialize the heap q, the current day i = 0, and the total eaten apples ans = 0.
Starting at day 0, let's walk through each day:
-
Day 0: We have
1apple that will expire after3days (i.e., it will rot onday 3). We add(3, 1)to the heap (the first value is the expiration day, and the second is the number of apples). Since there's only one apple and it's the only one in our heap, we eat it. Now,ans = 1. -
Day 1: We have
2new apples expiring by day3. Add(3, 2)to the heap. Remove the rotten apples from the top of the heap if any (but today, there are none). Now we eat one of the apples that expire by day3. Thus, we update the heap to remain with(3, 1)for this type of apple, andansbecomes2. -
Day 2: We have
3new apples that will expire by the end of today, day2. So we add(2, 3)to the heap. Before eating, we check for expired apples. Since it's day2, we remove the(2, 3)set as they have expired, and then we eat one apple from the remaining set(3, 1), leaving none of that type. Nowans = 3. -
Day 3: We do not have any new apples. We check for expired apples, and the heaps top is
(3, 1)which gets removed as it has expired today. Since there are no unexpired apples left, we can't eat any apples today. -
Day 4: No new apples, and the heap is empty. We don't have any apples to eat.
Therefore, using this strategy, the maximum number of apples we can eat is 3 (eaten on days 0, 1, and 2).
Solution Implementation
1from heapq import heappush, heappop
2
3class Solution:
4 def eatenApples(self, apples: List[int], days: List[int]) -> int:
5 # Get the total number of days for which we have apple data
6 n = len(days)
7 current_day = 0
8 total_eaten = 0
9 heap = [] # Priority queue to store apples and their expiration days
10
11 # Continue until we process all days or run out of apples
12 while current_day < n or heap:
13 # If we have apples that ripen today and are not rotten, add them to the heap
14 if current_day < n and apples[current_day] > 0:
15 # Store tuples of (expiration day, number of apples)
16 heappush(heap, (current_day + days[current_day] - 1, apples[current_day]))
17
18 # Remove rotten apples from the top of the heap (if any)
19 while heap and heap[0][0] < current_day:
20 heappop(heap)
21
22 # If we have any fresh apples, eat one
23 if heap:
24 expiration_day, apple_count = heappop(heap)
25 apple_count -= 1 # Eating one apple
26 total_eaten += 1 # Increase the total eaten apples count
27 # If there are apples remaining and they aren't expired, put them back in the heap
28 if apple_count > 0 and expiration_day > current_day:
29 heappush(heap, (expiration_day, apple_count))
30
31 # Move to the next day
32 current_day += 1
33
34 # Return the total number of apples eaten
35 return total_eaten
36
37# Example usage:
38# apples = [1, 2, 3, 5, 2]
39# days = [3, 2, 1, 4, 2]
40# solution = Solution()
41# print(solution.eatenApples(apples, days)) # Output will be the total apples eaten based on the input arrays
421class Solution {
2 public int eatenApples(int[] apples, int[] days) {
3 // PriorityQueue to store apple batches with their expiry days as the priority.
4 // It uses a comparator to ensure that the batch with the earliest expiry (smallest day) is at the top.
5 PriorityQueue<int[]> appleQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
6
7 int n = apples.length; // Number of days for which we have apple availability data.
8 int totalEatenApples = 0; // Counter to keep track of total apples eaten.
9 int currentDay = 0; // Current day, starting from day 0.
10
11 // Loop through each day until we have processed all days or the queue is empty.
12 while (currentDay < n || !appleQueue.isEmpty()) {
13 // If apples are available on the current day, add them to the queue.
14 if (currentDay < n && apples[currentDay] > 0) {
15 appleQueue.offer(new int[] {currentDay + days[currentDay] - 1, apples[currentDay]});
16 }
17
18 // Remove all batches from the queue that have expired by the current day.
19 while (!appleQueue.isEmpty() && appleQueue.peek()[0] < currentDay) {
20 appleQueue.poll();
21 }
22
23 // If there is at least one batch of apples that hasn't expired, eat one apple.
24 if (!appleQueue.isEmpty()) {
25 int[] batch = appleQueue.poll(); // Get the batch with the earliest expiry date.
26 totalEatenApples++; // Increment the count of eaten apples.
27 batch[1]--; // Decrement the count of apples in the batch since one is eaten.
28
29 // If there are still apples left in the batch and it hasn't expired, put it back in the queue.
30 if (batch[1] > 0 && batch[0] > currentDay) {
31 appleQueue.offer(batch);
32 }
33 }
34 // Move to the next day.
35 currentDay++;
36 }
37
38 return totalEatenApples; // Return the total number of apples eaten.
39 }
40}
411#include <vector>
2#include <queue>
3
4using std::vector;
5using std::priority_queue;
6using std::pair;
7using std::greater;
8
9class Solution {
10public:
11 int eatenApples(vector<int>& apples, vector<int>& days) {
12 // Priority queue to store apples with their expiration and count.
13 // The pair consists of the expiration day and the number of apples.
14 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> appleQueue;
15 int totalApplesEaten = 0;
16 int currentDate = 0;
17 int totalDays = days.size(); // Number of days we have apple and day information for.
18
19 // Continue until we have processed all days or until the queue is empty.
20 while (currentDate < totalDays || !appleQueue.empty()) {
21 // If we are within the day range and there are apples available on this day,
22 // add them to the priority queue with their expiration date.
23 if (currentDate < totalDays && apples[currentDate] > 0) {
24 int expirationDay = currentDate + days[currentDate] - 1;
25 appleQueue.emplace(expirationDay, apples[currentDate]);
26 }
27
28 // Remove all expired apples from the queue.
29 while (!appleQueue.empty() && appleQueue.top().first < currentDate) {
30 appleQueue.pop(); // Discard the expired apples.
31 }
32
33 // If there are any fresh apples left, eat one and update the count.
34 if (!appleQueue.empty()) {
35 auto [expiration, count] = appleQueue.top();
36 appleQueue.pop();
37 count--; // Eat one apple.
38 totalApplesEaten++; // Increment total eaten apple count.
39 if (count > 0 && expiration > currentDate) {
40 // If there are apples left that haven't expired, put them back into the queue.
41 appleQueue.emplace(expiration, count);
42 }
43 }
44
45 currentDate++; // Move to the next day.
46 }
47
48 return totalApplesEaten; // Return the total number of apples eaten.
49 }
50};
511// We are importing specific required types from the 'typescript-collections' library for priority queue implementation.
2import { PriorityQueue } from 'typescript-collections';
3
4interface AppleInfo {
5 expirationDay: number;
6 count: number;
7}
8
9// Eaten apples calculation function using vectors representing the number of apples and their days to rot.
10function eatenApples(apples: number[], days: number[]): number {
11 // Priority queue for apples based on their expiration, with the earliest expiration at the top.
12 const appleQueue = new PriorityQueue<AppleInfo>((a, b) => a.expirationDay - b.expirationDay);
13 let totalApplesEaten: number = 0;
14 let currentDate: number = 0;
15 // Calculate the number of days we have apple and day information.
16 const totalDays: number = days.length;
17
18 // Continue until all days are processed, or until the queue is empty.
19 while (currentDate < totalDays || !appleQueue.isEmpty()) {
20 // If within the days range and apples are available, add them with their expiration date.
21 if (currentDate < totalDays && apples[currentDate] > 0) {
22 const expirationDay = currentDate + days[currentDate] - 1;
23 appleQueue.enqueue({ expirationDay, count: apples[currentDate] });
24 }
25
26 // Remove all expired apples from the queue.
27 while (!appleQueue.isEmpty() && appleQueue.peek().expirationDay < currentDate) {
28 appleQueue.dequeue();
29 }
30
31 // If there are fresh apples, eat one and update the count.
32 if (!appleQueue.isEmpty()) {
33 let appleInfo = appleQueue.dequeue();
34 appleInfo.count--;
35 totalApplesEaten++;
36
37 // If there are uneaten apples which have not expired, put them back.
38 if (appleInfo.count > 0 && appleInfo.expirationDay > currentDate) {
39 appleQueue.enqueue(appleInfo);
40 }
41 }
42
43 // Move to the next day.
44 currentDate++;
45 }
46
47 // Return the total number of apples eaten.
48 return totalApplesEaten;
49}
50Which two pointer technique does Quick Sort use?
Time and Space Complexity
The time complexity of the code is O(n + k log k), where n is the length of the days array, and k is the total number of different apples received over the days. Each day up to day n, the operation either pushes (heappush) or pops (heappop) an item from the heap q, which takes O(log k) time. After day n, all elements in the heap q will be popped without any further pushes, so the complexity in that phase depends on the number of elements in the heap, which can be at most k. Since each element in the heap can only be pushed and popped once, the number of heap operations is limited to the number of elements k. Therefore, the total time spent on heap operations is O(k log k). Additionally, there is a constant amount of work done for each day i up to day n, contributing to the O(n) factor.
The space complexity of the code is O(k), as it requires storing each different apple's expiry date and count in the heap q. In the worst case, k could be as large as the number of days if we receive at least one apple on each day with different expiry dates. The heap size will never exceed the total number of apples because once an apple's expiry date has passed, it is removed from the heap.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.