Scale Engineer

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
ArrayHeap (Priority Queue)

Prompt

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.length
  • 1 <= n <= 2 * 104
  • 0 <= apples[i], days[i] <= 2 * 104
  • 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

import java.util.ArrayList;import java.util.List; class Solution {    public int eatenApples(int[] apples, int[] days) {        List<int[]> availableApples = new ArrayList<>();        int eatenCount = 0;        int n = apples.length;        int currentDay = 0;         // Loop until no more apples can be produced or eaten        while (true) {            // Add new apples that grow on the current day            if (currentDay < n && apples[currentDay] > 0) {                int expiryDay = currentDay + days[currentDay];                int appleCount = apples[currentDay];                availableApples.add(new int[]{expiryDay, appleCount});            }             // Find the non-rotten apple that will expire soonest            int bestAppleIndex = -1;            int earliestExpiry = Integer.MAX_VALUE;            for (int i = 0; i < availableApples.size(); i++) {                int[] batch = availableApples.get(i);                // Check if the batch is not rotten and has apples                if (batch[0] > currentDay && batch[1] > 0) {                    if (batch[0] < earliestExpiry) {                        earliestExpiry = batch[0];                        bestAppleIndex = i;                    }                }            }             // If a suitable apple is found, eat it            if (bestAppleIndex != -1) {                eatenCount++;                availableApples.get(bestAppleIndex)[1]--;            }             currentDay++;             // Check for termination condition            boolean hasEdibleApples = false;            for (int[] batch : availableApples) {                if (batch[0] > currentDay && batch[1] > 0) {                    hasEdibleApples = true;                    break;                }            }            if (currentDay >= n && !hasEdibleApples) {                break;            }        }        return eatenCount;    }}

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.

Solutions

class Solution {public  int eatenApples(int[] apples, int[] days) {    PriorityQueue<int[]> q =        new PriorityQueue<>(Comparator.comparingInt(a->a[0]));    int n = days.length;    int ans = 0, i = 0;    while (i < n || !q.isEmpty()) {      if (i < n && apples[i] > 0) {        q.offer(new int[]{i + days[i] - 1, apples[i]});      }      while (!q.isEmpty() && q.peek()[0] < i) {        q.poll();      }      if (!q.isEmpty()) {        var p = q.poll();        ++ans;        if (--p[1] > 0 && p[0] > i) {          q.offer(p);        }      }      ++i;    }    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 →

Next problem