Maximum Number of Eaten Apples — Problem & Solution
Maximum Number of Eaten Apples solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Number of Eaten Apples is a medium coding problem on arrays, greedy and heap, asked in Amazon, Google and Swiggy interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Heap
- Asked at: Amazon, Google, Swiggy
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tree grows apples[i] apples on day i, and those apples rot after days[i] days — so they may be eaten on days i through i + days[i] - 1. Some days it grows nothing, marked by apples[i] == 0 and days[i] == 0.
You eat at most one apple a day, and you may keep eating after day n - 1. 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
Example 2
Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5
Example 3
Input: apples = [2,1,10], days = [2,10,1]
Output: 4
Constraints
n == apples.length == days.length1 <= n <= 2 * 10^40 <= apples[i], days[i] <= 2 * 10^4days[i] == 0 if and only if apples[i] == 0.
Hints for Maximum Number of Eaten Apples
Hint 1
Each day, which batch should you eat from?
Hint 2
The one that rots soonest — anything else risks losing it entirely.
Hint 3
Keep the batches in a min-heap keyed on their rot day, and discard expired ones before each bite.
How to solve Maximum Number of Eaten Apples
Greedy with a min-heap keyed on rot day. Each day, add that day's batch, throw away everything that has already rotted, and eat one apple from the batch that expires soonest.
Approach
- For day
i < nwithapples[i] > 0, push(i + days[i], apples[i]). - Discard every batch whose rot day is at most the current day.
- If anything is left, eat one apple from the soonest-rotting batch and drop it when it empties.
- Continue past day
n - 1while any batch survives.
Why it works
Eating from the soonest-rotting batch is optimal by an exchange argument: choosing any other batch today risks losing the sooner one entirely, while the later batch is still there tomorrow. The loop must run past n - 1, since apples grown on the last day may stay edible for a long time.
Complexity
- Time —
O((n + maxDays) log n) - Space —
O(n)
Pitfalls
- A batch rots on day
i + days[i], so it is edible up to the day before. - Stopping the loop at day
n - 1throws away still-edible apples. - Days with
apples[i] == 0add nothing but still count as a day you may eat on.
Reference solution
Python
from typing import List
import heapq
def eatenApples(apples: List[int], days: List[int]) -> int:
n = len(apples)
heap = []
eaten = 0
day = 0
while day < n or heap:
if day < n and apples[day] > 0:
heapq.heappush(heap, (day + days[day], apples[day]))
while heap and heap[0][0] <= day:
heapq.heappop(heap)
if heap:
rot, cnt = heapq.heappop(heap)
eaten += 1
if cnt - 1 > 0:
heapq.heappush(heap, (rot, cnt - 1))
day += 1
return eatenJava
public static int eatenApples(int[] apples, int[] days) {
int n = apples.length;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int eaten = 0, day = 0;
while (day < n || !heap.isEmpty()) {
if (day < n && apples[day] > 0) heap.add(new int[] { day + days[day], apples[day] });
while (!heap.isEmpty() && heap.peek()[0] <= day) heap.poll();
if (!heap.isEmpty()) {
int[] top = heap.poll();
eaten++;
if (top[1] - 1 > 0) heap.add(new int[] { top[0], top[1] - 1 });
}
day++;
}
return eaten;
}C++
int eatenApples(vector<int>& apples, vector<int>& days) {
int n = (int) apples.size();
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
int eaten = 0, day = 0;
while (day < n || !heap.empty()) {
if (day < n && apples[day] > 0) heap.push({ day + days[day], apples[day] });
while (!heap.empty() && heap.top().first <= day) heap.pop();
if (!heap.empty()) {
auto top = heap.top();
heap.pop();
eaten++;
if (top.second - 1 > 0) heap.push({ top.first, top.second - 1 });
}
day++;
}
return eaten;
}JavaScript
var eatenApples = function(apples, days) {
var n = apples.length;
var batch = [];
var eaten = 0, day = 0, i;
while (day < n || batch.length > 0) {
if (day < n && apples[day] > 0) batch.push([day + days[day], apples[day]]);
for (i = batch.length - 1; i >= 0; i--) {
if (batch[i][0] <= day) batch.splice(i, 1);
}
if (batch.length > 0) {
var best = 0;
for (i = 1; i < batch.length; i++) if (batch[i][0] < batch[best][0]) best = i;
batch[best][1]--;
eaten++;
if (batch[best][1] === 0) batch.splice(best, 1);
}
day++;
}
return eaten;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms