There is a special kind of apple tree that grows apples every day for n days. On the ith day, the tree grows apples[i] apples that will rot after days[i] days, that is on day i + days[i] the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any apples, which are denoted by apples[i] == 0 and days[i] == 0.
You decided to eat at most one apple a day (to keep the doctors away). Note that you can keep eating after the first n days.
Given two integer arrays days and apples of length n, return the maximum number of apples you can eat.
Example 1:
Input: apples = [1,2,3,5,2], days = [3,2,1,4,2] Output: 7 Explanation: You can eat 7 apples: - On the first day, you eat an apple that grew on the first day. - On the second day, you eat an apple that grew on the second day. - On the third day, you eat an apple that grew on the second day. After this day, the apples that grew on the third day rot. - On the fourth to the seventh days, you eat apples that grew on the fourth day.
Example 2:
Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2] Output: 5 Explanation: You can eat 5 apples: - On the first to the third day you eat apples that grew on the first day. - Do nothing on the fouth and fifth days. - On the sixth and seventh days you eat apples that grew on the sixth day.
Constraints:
n == apples.length == days.length1 <= n <= 2 * 1040 <= apples[i], days[i] <= 2 * 104days[i] = 0 if and only if apples[i] = 0.Problem Overview: Each day an apple tree grows a certain number of apples, and every batch rots after a fixed number of days. You can eat at most one apple per day. The goal is to maximize the total number of apples eaten before they expire.
Approach 1: Day-by-Day Simulation with Expiry Scan (O(n^2) time, O(n) space)
A straightforward approach simulates every day and keeps track of all apples currently available along with their expiration dates. Each day, you scan the stored apples and pick the one that expires the soonest. The scan requires checking all active batches to find the earliest expiration. While this works conceptually, the repeated linear scans make the algorithm slow when many batches overlap. The idea still helps clarify the core rule: always consume the apple that will rot the earliest.
Approach 2: Greedy Strategy with Min-Heap (O(n log n) time, O(n) space)
The optimal strategy uses a greedy rule: eat the apple that expires the soonest. A min-heap efficiently enforces this rule by always exposing the batch with the smallest expiration day. Each heap entry stores (expiryDay, remainingCount). As you iterate through days, push the current day's apples into the heap with their calculated expiry (day + days[i]). Before eating, remove any entries whose expiry day is less than or equal to the current day since those apples have already rotted.
If the heap is not empty, pop the batch with the earliest expiry and eat one apple from it. If more apples remain in that batch, push it back with the updated count. Continue this process even after the input arrays finish, because apples grown earlier might still be edible. This greedy choice is optimal: eating a later-expiring apple while an earlier one exists risks losing the earlier apple permanently.
The heap ensures efficient operations. Insertion and removal both cost O(log n), and each batch is processed only a few times. The result is an overall complexity of O(n log n), which scales well even when the timeline extends beyond the initial number of days.
This pattern appears frequently in scheduling and resource allocation problems. The combination of greedy decision making with a heap (priority queue) is a standard way to handle "earliest deadline first" problems over an array of time-based events.
Recommended for interviews: The greedy min-heap solution is the expected approach. Interviewers want to see the insight that apples with the earliest expiration should always be consumed first. Mentioning the naive simulation shows you understand the baseline, but implementing the heap-based greedy scheduler demonstrates strong algorithmic thinking.
The main idea is to use a priority queue (min-heap) to store apples along with their expiration dates. Every day, you try to eat the apple that will rot soonest. The priority queue will help efficiently select and organize apple batches by their expiration date and count. This ensures that we maximize the number of apples eaten by prioritizing closer expiration dates.
This code implements a greedy algorithm using a min-heap (priority queue) to track apples by their expiration dates. It pushes a new batch of apples onto the heap for each day apples are available. It pops the apple batch with the earliest expiration that still has uneaten apples, increasing the count of eaten apples and re-pushing if there are any left unrotten. The heap automatically orders batches by the soonest to rot, ensuring effective selection each day.
Time Complexity: O(n log n), where n is the number of days. Each operation on a heap (insert, remove) takes logarithmic time, and we perform these operations each day.
Space Complexity: O(n), as in the worst case, all apple batches are stored in the heap.
We can greedily choose the apples that are closest to rotting among the unrotten apples, so that we can eat as many apples as possible.
Therefore, we can use a priority queue (min-heap) to store the rotting time of the apples and the corresponding number of apples. Each time, we take out the apples with the smallest rotting time from the priority queue, then decrement their quantity by one. If the quantity is not zero after decrementing, we put them back into the priority queue. If the apples have already rotted, we remove them from the priority queue.
The time complexity is O(n times log n + M), and the space complexity is O(n). Here, n is the length of the array days, and M = max(days).
| Approach | Complexity |
|---|---|
| Greedy Approach using Min-Heap | Time Complexity: O(n log n), where n is the number of days. Each operation on a heap (insert, remove) takes logarithmic time, and we perform these operations each day. |
| Greedy + Priority Queue | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Day-by-Day Simulation with Expiry Scan | O(n^2) | O(n) | Conceptual baseline or when constraints are very small |
| Greedy Approach using Min-Heap | O(n log n) | O(n) | General case; optimal strategy for handling earliest expiration efficiently |
Leetcode 1705. Maximum Number of Eaten Apples • Fraz • 5,278 views views
Watch 5 more video solutions →Practice Maximum Number of Eaten Apples with our built-in code editor and test cases.
Practice on FleetCode