Maximum Number of Eaten Apples solution and explanation
5 more videos on this problem
Leetcode 1705. Maximum Number of Eaten ApplesFraz · 10:44 · 5K views
LeetCode 1705. Maximum Number of Eaten ApplesHappy Coding · 16:16 · 1K views
Leetcode 1705. Maximum Number of Eaten Apples | Leetcode Weekly Contest 221INFO DECODER · 16:31 · 1K views
1705. Maximum Number of Eaten Apples (Leetcode Medium)Programming Live with Larry · 1:08:10 · 561 views
【每日一题】1705. Maximum Number of Eaten Apples, 12/28/2020Huifeng Guan · 18:26 · 399 views
LeetCode 1705: Maximum Number of Eaten ApplesAlitaCode · 27:03 · 12 views
The problem
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] = 0if and only ifapples[i] = 0.
Approach overview
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 1: Greedy Approach using Min-Heap
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.
import heapq
def eatenApples(apples, days):
pq = [] # priority queue as min-heap
eaten = 0
today = 0
while today < len(apples) or pq:
if today < len(apples) and apples[today] > 0:
heapq.heappush(pq, (today + days[today], apples[today]))
while pq and pq[0][0] <= today:
heapq.heappop(pq)
if pq:
rotten_day, count = heapq.heappop(pq)
count -= 1
if count > 0:
heapq.heappush(pq, (rotten_day, count))
eaten += 1
today += 1
return eaten
# Example usage
apples = [1, 2, 3, 5, 2]
days = [3, 2, 1, 4, 2]
print(eatenApples(apples, days))import java.util.PriorityQueue;
class Solution {
class AppleBatch {
int rotten_day;
int count;
AppleBatch(int rotten_day, int count) {
this.rotten_day = rotten_day;
this.count = count;
}
}
public int eatenApples(int[] apples, int[] days) {
PriorityQueue<AppleBatch> pq = new PriorityQueue<>((a, b) -> a.rotten_day - b.rotten_day);
int eaten = 0, today = 0;
while (today < apples.length || !pq.isEmpty()) {
if (today < apples.length && apples[today] > 0) {
pq.add(new AppleBatch(today + days[today], apples[today]));
}
while (!pq.isEmpty() && pq.peek().rotten_day <= today) {
pq.poll();
}
if (!pq.isEmpty()) {
AppleBatch batch = pq.poll();
if (--batch.count > 0) {
pq.add(batch);
}
eaten++;
}
today++;
}
return eaten;
}
public static void main(String[] args) {
int[] apples = {1, 2, 3, 5, 2};
int[] days = {3, 2, 1, 4, 2};
Solution solver = new Solution();
System.out.println(solver.eatenApples(apples, days));
}
}#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct AppleBatch {
int rotten_day;
int count;
};
class Compare {
public:
bool operator() (AppleBatch a, AppleBatch b) {
return a.rotten_day > b.rotten_day;
}
};
int eatenApples(vector<int>& apples, vector<int>& days) {
priority_queue<AppleBatch, vector<AppleBatch>, Compare> pq;
int eaten = 0, today = 0;
while (today < apples.size() || !pq.empty()) {
if (today < apples.size() && apples[today] > 0) {
pq.push(AppleBatch{today + days[today], apples[today]});
}
while (!pq.empty() && pq.top().rotten_day <= today) {
pq.pop();
}
if (!pq.empty()) {
AppleBatch batch = pq.top(); pq.pop();
if (--batch.count > 0 && batch.rotten_day > today) {
pq.push(batch);
}
eaten++;
}
today++;
}
return eaten;
}
int main() {
vector<int> apples = {1, 2, 3, 5, 2};
vector<int> days = {3, 2, 1, 4, 2};
cout << eatenApples(apples, days) << endl;
return 0;
}function eatenApples(apples, days) {
const pq = [];
let eaten = 0;
let today = 0;
while (today < apples.length || pq.length > 0) {
if (today < apples.length && apples[today] > 0) {
pq.push({ rottenDay: today + days[today], count: apples[today] });
}
pq.sort((a, b) => a.rottenDay - b.rottenDay);
while (pq.length > 0 && pq[0].rottenDay <= today) {
pq.shift();
}
if (pq.length > 0) {
let batch = pq.shift();
batch.count--;
if (batch.count > 0) {
pq.unshift(batch);
}
eaten++;
}
today++;
}
return eaten;
}
// Example usage
const apples = [1, 2, 3, 5, 2];
const days = [3, 2, 1, 4, 2];
console.log(eatenApples(apples, days));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Define a structure for pairs
typedef struct {
int rotten_day;
int count;
} AppleBatch;
// Custom comparison function for min heap
int cmp(const void *a, const void *b) {
return ((AppleBatch*)a)->rotten_day - ((AppleBatch*)b)->rotten_day;
}
// Priority Queue (Min heap) initialization
AppleBatch min_heap[20000];
int heap_size = 0;
void push(AppleBatch batch) {
min_heap[heap_size++] = batch;
for (int i = heap_size - 1; i > 0;) {
int p = (i - 1) >> 1;
if (min_heap[i].rotten_day >= min_heap[p].rotten_day) break;
AppleBatch tmp = min_heap[i];
min_heap[i] = min_heap[p];
min_heap[p] = tmp;
i = p;
}
}
void siftDown(int i) {
while (2 * i + 1 < heap_size) {
int a = 2 * i + 1, b = a + 1;
int min_i = (b < heap_size && cmp(&min_heap[b], &min_heap[a]) < 0) ? b : a;
if (cmp(&min_heap[min_i], &min_heap[i]) >= 0) break;
AppleBatch tmp = min_heap[i];
min_heap[i] = min_heap[min_i];
min_heap[min_i] = tmp;
i = min_i;
}
}
AppleBatch pop() {
AppleBatch answer = min_heap[0];
min_heap[0] = min_heap[--heap_size];
siftDown(0);
return answer;
}
bool empty() {
return heap_size == 0;
}
AppleBatch top() {
return min_heap[0];
}
int eatenApples(int* apples, int applesSize, int* days, int daysSize) {
int today = 0, eaten = 0;
while (today < applesSize || !empty()) {
if (today < applesSize && apples[today] > 0) {
push((AppleBatch){today + days[today], apples[today]});
}
while (!empty() && top().rotten_day <= today) {
pop();
}
if (!empty()) {
AppleBatch batch = pop();
if (--batch.count > 0 && batch.rotten_day > today) {
push(batch);
}
eaten++;
}
today++;
}
return eaten;
}
int main() {
int apples[] = {1, 2, 3, 5, 2};
int days[] = {3, 2, 1, 4, 2};
int n = sizeof(apples) / sizeof(apples[0]);
printf("%d\n", eatenApples(apples, n, days, n));
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int EatenApples(int[] apples, int[] days) {
var pq = new SortedSet<(int rottenDay, int count)>(Comparer<(int, int)>.Create((a, b) => a.rottenDay == b.rottenDay ? a.count.CompareTo(b.count) : a.rottenDay.CompareTo(b.rottenDay)));
int eaten = 0, today = 0;
while (today < apples.Length || pq.Count > 0) {
if (today < apples.Length && apples[today] > 0) {
pq.Add((today + days[today], apples[today]));
}
while (pq.Count > 0 && pq.Min.rottenDay <= today) {
pq.Remove(pq.Min);
}
if (pq.Count > 0) {
var batch = pq.Min;
pq.Remove(batch);
if (--batch.count > 0) {
pq.Add(batch);
}
eaten++;
}
today++;
}
return eaten;
}
static void Main() {
var solver = new Solution();
int[] apples = {1, 2, 3, 5, 2};
int[] days = {3, 2, 1, 4, 2};
Console.WriteLine(solver.EatenApples(apples, days));
}
}This Python solution deploys a min-heap through the heapq module to track apple batches by their expirations. Each day we either add new apples, ignore expired ones, or consume one from the soonest-to-expire batch. The routine comprehensively captures and exploits day-to-day transaction dynamics with efficient prioritization.
Time Complexity: O(n log n) for heap insertions and deletions each day.
Space Complexity: O(n) from heap storage of apple batches.
Approach 2: Greedy + Priority Queue
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).
func eatenApples(apples []int, days []int) int {
var h hp
ans, n := 0, len(apples)
for i := 0; i < n || len(h) > 0; i++ {
if i < n && apples[i] > 0 {
heap.Push(&h, pair{i + days[i] - 1, apples[i]})
}
for len(h) > 0 && h[0].first < i {
heap.Pop(&h)
}
if len(h) > 0 {
h[0].second--
if h[0].first == i || h[0].second == 0 {
heap.Pop(&h)
}
ans++
}
}
return ans
}
type pair struct {
first int
second int
}
type hp []pair
func (a hp) Len() int { return len(a) }
func (a hp) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a hp) Less(i, j int) bool { return a[i].first < a[j].first }
func (a *hp) Push(x any) { *a = append(*a, x.(pair)) }
func (a *hp) Pop() any { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach using Min-Heap | Time Complexity: O(n log n) for heap insertions and deletions each day. |
| Greedy + Priority Queue | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Number of Eaten Apples easy or hard?
Maximum Number of Eaten Apples is categorized as a Medium difficulty problem. The main challenge is recognizing the greedy strategy and implementing it efficiently with a heap to handle expiration deadlines.
Maximum Number of Eaten Apples Python/Java solution
Implement the greedy strategy using a priority queue. In Python, the heapq module manages the min-heap, while Java uses PriorityQueue. Each entry stores the expiration day and remaining apple count, and you simulate eating one apple per day while maintaining the heap.
How to solve Maximum Number of Eaten Apples in O(n log n)?
Iterate day by day and push newly grown apples into a min-heap with their expiration day. Before eating, remove any heap entries that have already expired. Always consume one apple from the batch with the earliest expiration. Reinsert the batch if apples remain, ensuring heap operations keep the process efficient.
What is the best approach for Maximum Number of Eaten Apples?
The best approach uses a greedy strategy with a min-heap (priority queue). Each heap entry stores the expiration day and remaining apples for that batch. On every day, remove expired batches and eat the apple that expires the earliest. This guarantees the maximum number of apples eaten with O(n log n) time complexity.
Is Maximum Number of Eaten Apples asked at Google/Amazon/Meta?
Maximum Number of Eaten Apples is a common medium-level greedy and heap problem similar to scheduling questions asked in companies like Amazon, Google, and Meta. The problem tests understanding of priority queues and deadline-based greedy strategies.
What data structure is used in Maximum Number of Eaten Apples?
The key data structure is a min-heap (priority queue). It keeps apple batches sorted by their expiration day so the algorithm can always pick the apple that will rot the soonest.
What is the time complexity of Maximum Number of Eaten Apples?
The optimal solution runs in O(n log n) time using a min-heap. Each batch of apples is inserted and possibly reinserted into the heap, and heap operations take O(log n). Space complexity is O(n) to store active apple batches.