Maximum Number of Eaten Apples - Practice Coding Problems

Maximum Number of Eaten Apples - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: apples = [1,2,3,5], days = [3,2,1,4]

› Output: 7

💡 Note: Day 0: eat apple from batch 2 (expires day 2). Day 1: eat apple from batch 1 (expires day 3). Day 2: eat apple from batch 1 (expires day 3). Day 3: eat apple from batch 0 (expires day 3). Day 4: eat apple from batch 3 (expires day 7). Day 5: eat apple from batch 3. Day 6: eat apple from batch 3. Total: 7 apples.

Example 2 — Some Days No Apples

$ Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]

› Output: 5

💡 Note: Days 0-2: eat one apple each day from first batch (3 apples expire day 3). Days 3-4: no apples available. Day 5: add second batch (2 apples expire day 7). Days 5-6: eat from second batch. Total: 5 apples.

Example 3 — Single Day

$ Input: apples = [1], days = [1]

› Output: 1

💡 Note: Day 0: eat the single apple (expires day 1). No more apples available after day 0. Total: 1 apple.

Constraints

1 ≤ n ≤ 2 × 10⁴
0 ≤ apples[i] ≤ 2 × 10⁴
1 ≤ days[i] ≤ 2 × 10⁴
apples[i] == 0 if and only if days[i] == 0

Visualization

Tap to expand

Understanding the Visualization

Input

Apple arrays: apples=[1,2,3,5], days=[3,2,1,4]

Process

Use greedy strategy with priority queue to eat expiring apples first

Output

Maximum apples eaten: 7

Key Takeaway

🎯 Key Insight: Always eat the apple that expires soonest to maximize total consumption before spoilage

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is to always eat the apple that expires soonest to maximize total consumption. Best approach uses a min-heap (priority queue) to efficiently track apple batches by expiration day. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible eating sequences and find the one with maximum apples eaten
Greedy with Priority Queue (Min-Heap)	O(n log n)	O(n)	Use a min-heap to always eat the apple that expires soonest

Brute Force - Try All Combinations — Algorithm Steps

For each day from 0 onwards, consider all available apple batches
Recursively try eating from each batch or skipping the day
Track the maximum apples eaten across all possible sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Day 0

Try eating from each available batch or skip

Recursion

For each choice, recursively solve remaining days

Maximum

Return the path with maximum apples eaten

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int backtrack(int day, int appleBatches[][2], int batchCount) {
    int validBatches[100][2];
    int validCount = 0;
    
    for (int i = 0; i < batchCount; i++) {
        if (appleBatches[i][1] > day) {
            validBatches[validCount][0] = appleBatches[i][0];
            validBatches[validCount][1] = appleBatches[i][1];
            validCount++;
        }
    }
    
    if (validCount == 0) {
        return 0;
    }
    
    int maxEaten = 0;
    
    for (int i = 0; i < validCount; i++) {
        int newBatches[100][2];
        int newCount = 0;
        
        for (int j = 0; j < validCount; j++) {
            if (i == j) {
                if (validBatches[j][0] > 1) {
                    newBatches[newCount][0] = validBatches[j][0] - 1;
                    newBatches[newCount][1] = validBatches[j][1];
                    newCount++;
                }
            } else {
                newBatches[newCount][0] = validBatches[j][0];
                newBatches[newCount][1] = validBatches[j][1];
                newCount++;
            }
        }
        
        int eaten = 1 + backtrack(day + 1, newBatches, newCount);
        maxEaten = max(maxEaten, eaten);
    }
    
    maxEaten = max(maxEaten, backtrack(day + 1, validBatches, validCount));
    
    return maxEaten;
}

int solution(int* apples, int* days, int n) {
    int appleBatches[100][2];
    int batchCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (apples[i] > 0) {
            appleBatches[batchCount][0] = apples[i];
            appleBatches[batchCount][1] = i + days[i];
            batchCount++;
        }
    }
    
    return backtrack(0, appleBatches, batchCount);
}

int main() {
    char line[1000];
    int apples[100], days[100];
    int n = 0;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        apples[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int m = 0;
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\n ");
    while (token != NULL) {
        days[m++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    printf("%d\n", solution(apples, days, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each day we have multiple choices creating exponential branching

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth proportional to number of days

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler