Maximum Number of Eaten Apples

Med

#1563Time: O(D * n), where `D` is the last day an apple can be eaten (roughly `n + max(days)`) and `n` is the length of the input arrays. The outer loop runs up to `D` times, and inside it, we scan a list of size up to `n`. This quadratic-like complexity is too slow for the given constraints.Space: O(n), where n is the length of the input arrays. In the worst case, we might store a batch of apples for each of the n days.

Patterns

Greedy

Data structures

Array Heap (Priority Queue)

Prompt

There is a special kind of apple tree that grows apples every day for n days. On the i^th 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.length
1 <= n <= 2 * 10⁴
0 <= apples[i], days[i] <= 2 * 10⁴
days[i] = 0 if and only if apples[i] = 0.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process day by day in a straightforward manner. It maintains a simple list of all available apple batches, where a batch consists of apples that grew on the same day and share the same expiry date. For each day, it first adds any new apples that have grown. Then, to decide which apple to eat, it performs a linear scan through the entire list of available batches to find a non-rotten apple that will expire the soonest. After eating one, it moves to the next day. This process continues until no more apples can be grown or eaten.

Algorithm

Initialize eatenCount = 0, currentDay = 0, and an empty list availableApples to store pairs of [expiryDate, count].
Start a loop to simulate the passage of time, day by day.
Inside the loop for currentDay:
- If currentDay is less than n and apples[currentDay] is positive, add a new batch [currentDay + days[currentDay], apples[currentDay]] to the availableApples list.
- Linearly scan the availableApples list to find the batch that is not rotten (expiryDate > currentDay) and has the earliest expiryDate.
- If such an apple batch is found, increment eatenCount and decrement the apple count of that batch.
- Increment currentDay.
The loop terminates when currentDay is past n and there are no more edible apples left in the availableApples list.
Return the total eatenCount.

Walkthrough

We use a simple list, for instance, an ArrayList in Java, to store pairs of [expiryDate, count] for each batch of apples. We then loop through time, day by day, starting from day 0.

In each iteration for day d:

Add New Apples: If d is within the n days of growth (d < n) and apples[d] is positive, we calculate the expiry date d + days[d] and add a new entry [expiryDate, apples[d]] to our list.
Find Best Apple: We search for the best apple to eat. We initialize a variable bestAppleIndex to -1 and earliestExpiry to infinity. We then iterate through our list of apple batches. For each batch, we check if it's not rotten (i.e., expiryDate > d) and if its expiryDate is earlier than the current earliestExpiry. If both conditions are met, we update earliestExpiry and bestAppleIndex.
Eat Apple: If we found a valid apple to eat (bestAppleIndex != -1), we increment our total count of eaten apples and decrement the count of the chosen apple batch.
Advance Day: We increment the day d to move to the next day.

The simulation stops when we are past the n days of growth and a check reveals there are no more edible apples left in our list.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int eatenApples(int[] apples, int[] days) {6        List<int[]> availableApples = new ArrayList<>();7        int eatenCount = 0;8        int n = apples.length;9        int currentDay = 0;10 11        // Loop until no more apples can be produced or eaten12        while (true) {13            // Add new apples that grow on the current day14            if (currentDay < n && apples[currentDay] > 0) {15                int expiryDay = currentDay + days[currentDay];16                int appleCount = apples[currentDay];17                availableApples.add(new int[]{expiryDay, appleCount});18            }19 20            // Find the non-rotten apple that will expire soonest21            int bestAppleIndex = -1;22            int earliestExpiry = Integer.MAX_VALUE;23            for (int i = 0; i < availableApples.size(); i++) {24                int[] batch = availableApples.get(i);25                // Check if the batch is not rotten and has apples26                if (batch[0] > currentDay && batch[1] > 0) {27                    if (batch[0] < earliestExpiry) {28                        earliestExpiry = batch[0];29                        bestAppleIndex = i;30                    }31                }32            }33 34            // If a suitable apple is found, eat it35            if (bestAppleIndex != -1) {36                eatenCount++;37                availableApples.get(bestAppleIndex)[1]--;38            }39 40            currentDay++;41 42            // Check for termination condition43            boolean hasEdibleApples = false;44            for (int[] batch : availableApples) {45                if (batch[0] > currentDay && batch[1] > 0) {46                    hasEdibleApples = true;47                    break;48                }49            }50            if (currentDay >= n && !hasEdibleApples) {51                break;52            }53        }54        return eatenCount;55    }56}

Complexity

Time

O(D * n), where `D` is the last day an apple can be eaten (roughly `n + max(days)`) and `n` is the length of the input arrays. The outer loop runs up to `D` times, and inside it, we scan a list of size up to `n`. This quadratic-like complexity is too slow for the given constraints.

Space

O(n), where n is the length of the input arrays. In the worst case, we might store a batch of apples for each of the n days.

Trade-offs

Pros

Conceptually simple and easy to follow.
Directly translates the problem statement into code without complex data structures.

Cons

Extremely inefficient due to the nested loop structure (simulating days and scanning the list of apples).
The time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on most platforms.

A much more efficient approach is to use a greedy strategy. The optimal strategy is to always eat an apple that will rot the soonest. This maximizes the chances of eating apples that would otherwise be wasted, while preserving apples with a longer shelf life for later days. A min-priority queue is the perfect data structure to implement this. It can store apple batches (represented by their expiry date and count) and allows for efficient retrieval of the batch with the earliest expiry date.

Algorithm

Initialize a min-priority queue pq to store [expiryDate, count] pairs, ordered by expiryDate.
Initialize eatenCount = 0 and the current day d = 0.
Loop as long as there are days left for apples to grow (d < n) or there are still apples in the pq.
Inside the loop:
- If d < n and apples[d] > 0, add the new batch [d + days[d], apples[d]] to the pq.
- Remove all rotten apple batches from the top of the pq. A batch is rotten if its expiryDate <= d.
- If the pq is not empty after removing rotten ones, it means there's an edible apple. Eat one from the top batch (which expires soonest).
- To do this, increment eatenCount, poll() the top batch, decrement its count, and if the count is still positive, offer() it back to the pq.
- Increment the day d.
Return eatenCount after the loop terminates.

Walkthrough

This approach uses a min-priority queue (min-heap) to keep track of the available apples. The priority queue will store arrays or objects containing two pieces of information: the expiry date and the number of apples in that batch. The queue is ordered based on the expiry date, so the batch that will expire soonest is always at the top.

The simulation proceeds day by day:

Data Structure: We use a PriorityQueue<int[]> in Java, where each int[] is a pair {expiryDate, count}. We provide a custom comparator to sort by expiryDate.
Iteration: We loop with a day counter d, starting from 0. The loop continues as long as we are within the n days of growth or there are still apples in our priority queue.
Add New Apples: On day d, if d < n and apples[d] > 0, we add a new batch {d + days[d], apples[d]} to the priority queue. This operation takes O(log k) time, where k is the current size of the queue.
Remove Rotten Apples: Before eating, we must discard any apples that have already rotted. We peek at the top of the queue and, as long as it's not empty and its expiry date is less than or equal to the current day d, we poll it from the queue.
Eat an Apple: After cleaning up, if the queue is not empty, we can eat an apple. We poll the top batch (the one expiring soonest), increment our eatenApples count, and decrement its apple count. If apples remain in this batch (count > 0), we add it back to the queue.

This process ensures that on any given day, we make the optimal greedy choice, leading to the maximum number of eaten apples.

1import java.util.PriorityQueue;2 3class Solution {4    public int eatenApples(int[] apples, int[] days) {5        // Min-heap storing pairs of [expiryDay, appleCount]6        // Ordered by expiryDay7        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);8        9        int eatenCount = 0;10        int n = apples.length;11        int i = 0;12        13        // Loop continues as long as there are days left to grow apples (i < n)14        // or there are still apples in the priority queue to be eaten.15        while (i < n || !pq.isEmpty()) {16            // 1. Add apples that grow today17            if (i < n && apples[i] > 0) {18                int expiryDay = i + days[i];19                int appleCount = apples[i];20                pq.offer(new int[]{expiryDay, appleCount});21            }22            23            // 2. Remove rotten apples from the top of the queue24            while (!pq.isEmpty() && pq.peek()[0] <= i) {25                pq.poll();26            }27            28            // 3. Eat one apple if available29            if (!pq.isEmpty()) {30                eatenCount++;31                int[] earliestBatch = pq.poll();32                earliestBatch[1]--;33                // If there are still apples left in this batch, add it back34                if (earliestBatch[1] > 0) {35                    pq.offer(earliestBatch);36                }37            }38            39            // Move to the next day40            i++;41        }42        43        return eatenCount;44    }45}

Complexity

Time

O(D * log n), where `D` is the last day an apple can be eaten (at most `n + max(days)`) and `n` is the number of days apples grow. The main loop runs `D` times, and each iteration involves a few priority queue operations, which take `O(log n)` time. This is efficient enough for the given constraints.

Space

O(n), where n is the number of days apples grow. In the worst-case scenario, the priority queue might need to store a distinct batch of apples for each of the `n` days.

Trade-offs

Pros

Highly efficient and provides the optimal solution.
The greedy choice is provably correct for this problem.
Passes all test cases within the given time and memory constraints.

Cons

Requires knowledge of priority queues (min-heaps).
Slightly more complex to implement compared to a simple list-based simulation.

Solutions

Solution

1class Solution {2public3  int eatenApples(int[] apples, int[] days) {4    PriorityQueue<int[]> q =5        new PriorityQueue<>(Comparator.comparingInt(a->a[0]));6    int n = days.length;7    int ans = 0, i = 0;8    while (i < n || !q.isEmpty()) {9      if (i < n && apples[i] > 0) {10        q.offer(new int[]{i + days[i] - 1, apples[i]});11      }12      while (!q.isEmpty() && q.peek()[0] < i) {13        q.poll();14      }15      if (!q.isEmpty()) {16        var p = q.poll();17        ++ans;18        if (--p[1] > 0 && p[0] > i) {19          q.offer(p);20        }21      }22      ++i;23    }24    return ans;25  }26}

1using pii = pair < int , int > ; class Solution { public: int eatenApples ( vector < int >& apples , vector < int >& days ) { priority_queue < pii , vector < pii > , greater < pii >> q ; int n = days . size (); int ans = 0 , i = 0 ; while ( i < n || ! q . empty ()) { if ( i < n && apples [ i ]) q . emplace ( i + days [ i ] - 1 , apples [ i ]); while ( ! q . empty () && q . top (). first < i ) q . pop (); if ( ! q . empty ()) { auto [ t , v ] = q . top (); q . pop (); -- v ; ++ ans ; if ( v && t > i ) q . emplace ( t , v ); } ++ i ; } return ans ; } };

1class Solution:2    def eatenApples(self, apples: List[int], days: List[int]) -> int: n = len(days) i = ans = 0 q = [] while i < n or q: if i < n and apples[i]: heappush(q, (i + days[i] - 1, apples[i])) while q and q[0][0] < i: heappop(q) if q: t, v = heappop(q) v -= 1 ans += 1 if v and t > i: heappush(q, (t, v)) i += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem