Maximum Number of Eaten Apples

Medium
978.

Maximum Number of Eaten Apples

MediumArrayGreedyHeap (Priority Queue)AmazonGoogleSwiggy

Maximum Number of Eaten Apples is a medium coding problem on arrays, greedy and heap, asked in Amazon, Google and Swiggy interviews.

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.length
  • 1 <= n <= 2 * 10^4
  • 0 <= apples[i], days[i] <= 2 * 10^4
  • days[i] == 0 if and only if apples[i] == 0.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} apples
 * @param {number[]} days
 * @return {number}
 */
var eatenApples = function(apples, days) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 2 * 10^4
  • 0 <= apples[i], days[i] <= 2 * 10^4
  • days[i] == 0 if and only if apples[i] == 0.

Hints for Maximum Number of Eaten Apples

  1. Hint 1

    Each day, which batch should you eat from?

  2. Hint 2

    The one that rots soonest — anything else risks losing it entirely.

  3. 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

  1. For day i < n with apples[i] > 0, push (i + days[i], apples[i]).
  2. Discard every batch whose rot day is at most the current day.
  3. If anything is left, eat one apple from the soonest-rotting batch and drop it when it empties.
  4. Continue past day n - 1 while 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 - 1 throws away still-edible apples.
  • Days with apples[i] == 0 add 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 eaten

Java

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