Watch 6 video solutions for Maximum Number of Eaten Apples, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by Fraz has 5,278 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |