Skip to main content

Heaps

Maximum Number of Eaten Apples Problem Solution In C++/Java/Python/Javascript

Problem Description

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, meaning they become rotten on day i + days[i] and can no longer be eaten. On some days, no apples are grown; this is indicated by apples[i] == 0 and days[i] == 0.
You decide to eat at most one apple per day to keep the doctors away. Note that you can continue eating after the first n days as long as there are unrotted apples available.
Given two integer arrays, days and apples, both of length n, return the maximum number of apples you can eat.

Example

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.

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^4
  • 0 <= apples[i], days[i] <= 2 * 10^4
  • days[i] = 0 if and only if  apples[i] = 0.
💡
Try it Yourself
The problem involves maximizing the number of apples you can eat from a tree that produces a new batch each day, with each apple having a limited lifespan before it rots. Your goal is to eat at most one apple per day—potentially even after the production period ends—while ensuring you consume them before they spoil. An effective strategy is to prioritize eating the apples that will expire soonest.

Optimal Approach

Intuition

Imagine you buy fruits at home that come with an expiration label. Naturally, if you have two fruits—one that expires tomorrow and another that expires in a week—you’d want to eat the one expiring tomorrow first. This way, you avoid wasting the fruit that will go bad soon while saving the longer-lasting one for later. So our plan should always be of finding out the the fruits that rots earlier. In this way we can ensure that our fruits are least wasted.

Now in coding terms naturally what we can do is we maintain a simple list where each element represents a batch of apples with its expiration day and remaining count, for example, as a pair [expiry_day,remaining_apples]. Every day, we first remove any batches that have already expired, then add the new batch of apples (if available) with their corresponding expiration day. To decide which apple to eat, we scan through the list to locate the batch that is closest to its expiration—this ensures we are consuming the apples that will rot the soonest.

Dry Run

Let’s consider an example:

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

Day 0:

  • New Batch:
    Apples from day 0: 1 apple, expires at day 0+3=30 + 3 = 30+3=3.
    List becomes: [(3, 1)]
  • Eat an Apple:
    Consume 1 apple from the batch (expires at 3).
    List becomes empty.
    Total eaten: 1

Day 1:

  • New Batch:
    Apples from day 1: 2 apples, expires at 1+2=31 + 2 = 31+2=3.
    List becomes: [(3, 2)]
  • Eat an Apple:
    Consume 1 apple from the batch. Update batch to: (3, 1)
    Total eaten: 2

Day 2:

  • New Batch:
    Apples from day 2: 3 apples, expires at 2+1=32 + 1 = 32+1=3.
    Append to list: now we have [(3, 1), (3, 3)]
  • Eat an Apple:
    Ideally, we want to eat from the batch that’s expiring soonest. Both batches here expire on day 3, so you eat one apple from the first batch:
    Batch (3, 1) becomes (3, 0) and is removed.
    List becomes: [(3, 3)]
    Total eaten: 3

Day 3:

  • Remove Rotten Apples:
    At the start of day 3, any batch with expiry ≤ 3 is no longer usable. So the batch (3, 3) is removed.
  • New Batch:
    Apples from day 3: 5 apples, expires at 3+4=73 + 4 = 73+4=7.
    List becomes: [(7, 5)]
  • Eat an Apple:
    Consume 1 apple, update batch to (7, 4).
    Total eaten: 4

Day 4:

  • New Batch:
    Apples from day 4: 2 apples, expires at 4+2=64 + 2 = 64+2=6.
    List now would be: [(7, 4), (6, 2)]
  • Decision:
    Now, note that even though the batch (7, 4) is at the front, the batch (6, 2) will rot sooner (expiry = 6 vs. 7).
    Ideally, you’d want to eat from the batch expiring on day 6 first.

If we simply use a list (or vector) and traverse it each day to decide which apple to eat, it can become computationally expensive—especially when there are many batches.
Scanning the entire list every day to find the batch with the earliest expiry can lead to poor performance for large inputs.

To efficiently pick the batch with the earliest expiry every day, we want a data structure that always gives us the minimum element (i.e., the batch with the smallest expiry date) quickly, without scanning through the entire list.

A min-heap (or priority queue) is perfect for this task because it always allows us to access the element with the minimum expiry date in constant time. What we just need to do is always put the the fruits along with their expiry date in this data structure and always it will give us the fruits with minimum expiry date . In this manner our computations are reduced significantly.

What is Heap?

A heap is a specialized tree-based data structure often used to implement priority queues. Heaps are usually implemented as complete binary trees (every level is fully filled except possibly the last, and all nodes are as far left as possible), which allows them to be efficiently stored in an array. With a heap, you can quickly access the minimum or maximum element in constant time, and insertion or deletion operations take logarithmic time. This makes heaps extremely useful in algorithms that require repeated retrieval of the "best" element, like scheduling tasks or sorting data with heapsort.

What is min-heap?
A min-heap is a specialized binary tree-based data structure where the smallest element is always at the root. This means that for any given node in the tree, its value is less than or equal to the values of its children. Because of this property, you can quickly access the minimum element at any time. Additionally, a min-heap is usually implemented as a complete binary tree, which means all levels of the tree are fully filled except possibly the last level, and all nodes in the last level are as far left as possible.

What is max-heap?
A max-heap is a complete binary tree data structure where every parent node has a value greater than or equal to its children, ensuring that the largest element is always at the root. This property makes it easy to quickly access the maximum element. Like a min-heap, a max-heap is typically implemented using an array, which efficiently represents the complete binary tree.

General Operations on Heap:

  • Insertion:
    Inserting an element takes O(log n) time because after placing the new element at the end of the array, you "bubble up" (or "sift up") to restore the heap property.
  • Removal (Extract-Min/Extract-Max):
    Removing the root element (the minimum in a min-heap or maximum in a max-heap) also takes O(log n) time since after removal, you "bubble down" (or "sift down") the last element placed at the root to reestablish the heap property.
  • Peek (Find-Min/Find-Max):
    Retrieving the root element is an O(1) operation because it is always at the front of the array.
  • Building a Heap:
    Building a heap from an unsorted array can be done in O(n) time using a bottom-up heapify process.
  • Space Complexity:
    The heap uses O(n) space to store n elements.

Approach

Step 1: Initialization

  • Determine the number of days, n, from the size of the apples vector.
  • Create an empty list, applesList, to store pairs of (expiry day, remaining apples).
  • Set totalEaten (the count of eaten apples) to 0 and initialize the day counter to 0.

Step 2: Main Loop Condition

  • Continue looping while there are still days within the production period (day < n) or there are remaining apple batches in applesList.

Step 3: Removing Rotten Apples

  • For each day, remove batches from applesList whose expiry day is less than or equal to the current day, as these apples have rotted.

Step 4: Adding Today's Apples

  • If the current day is within the production period (day < n) and apples are produced (apples[day] > 0), add a new batch to applesList.
  • The batch is represented as a pair where the expiry day is calculated as day + days[day] and the quantity is apples[day].

Step 5: Eating an Apple

  • If there is at least one batch available in applesList, eat one apple from the first batch (which is assumed to have the earliest expiry).
  • Decrease the remaining apple count of that batch by one.
  • If the batch is exhausted (remaining apples become 0), remove it from applesList.
  • Increment the totalEaten counter by one.

Step 6: Advancing to the Next Day

  • Increment the day counter to move on to the next day.

Step 7: Termination and Result

  • Once all days have been processed and there are no remaining apple batches, exit the loop.
  • Return the total number of apples eaten as the final result.

Dry Run

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

This input is used for the step-by-step dry run given below.

Step 1: Initialization

  • n = 5 (length of apples array)
  • applesList = [] (to store {expiry day, remaining apples})
  • totalEaten = 0
  • day = 0

Step 2: Day 0

  • Remove expired apples → applesList = [] (nothing to remove)
  • Add today's apples → Add (3,1) (expires on day 3)
  • Eat one apple → Reduce (3,1) to (3,0), remove it
  • Increment totalEaten = 1
  • Move to day = 1

Step 3: Day 1

  • Remove expired apples → applesList = [] (nothing to remove)
  • Add today's apples → Add (3,2) (expires on day 3)
  • Eat one apple → Reduce (3,2) to (3,1)
  • Increment totalEaten = 2
  • Move to day = 2

Step 4: Day 2

  • Remove expired apples → applesList = [(3,1)] (still valid)
  • Add today's apples → Add (3,3) (expires on day 3)
  • Eat one apple → Reduce (3,1) to (3,0), remove it
  • Increment totalEaten = 3
  • Move to day = 3

Step 5: Day 3

  • Remove expired apples → Remove (3,3) as today is expiry day
  • Add today's apples → Add (7,5) (expires on day 7)
  • Eat one apple → Reduce (7,5) to (7,4)
  • Increment totalEaten = 4
  • Move to day = 4

Step 6: Day 4

  • Remove expired apples → applesList = [(7,4)] (still valid)
  • Add today's apples → Add (6,2) (expires on day 6)
  • Eat one apple → Reduce (6,2) to (6,1)
  • Increment totalEaten = 5
  • Move to day = 5

Step 7: Day 5

  • Remove expired apples → applesList = [(6,1), (7,4)] (still valid)
  • Add today's apples → No new apples
  • Eat one apple → Reduce (6,1) to (6,0), remove it
  • Increment totalEaten = 6
  • Move to day = 6

Step 8: Day 6

  • Remove expired apples → applesList = [(7,4)] (still valid)
  • Add today's apples → No new apples
  • Eat one apple → Reduce (7,4) to (7,3)
  • Increment totalEaten = 7
  • Move to day = 7

Step 9: Day 7

  • Remove expired apples → Remove (7,3) as today is expiry day
  • Add today's apples → No new apples
  • Eat one apple → No apples available
  • Stop processing since applesList is empty and day > n

Final Output

  • totalEaten = 7
Code for All Languages
Maximum Number of Eaten Apples solution in C++:Optimal 
class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
    int n = apples.size();
    vector<pair<int, int>> applesList; // {expiry_day, remaining_apples}
    int totalEaten = 0;
    int day = 0;

    while (day < n || !applesList.empty()) {
        // Remove rotten apples
        while (!applesList.empty() && applesList.front().first <= day) {
            applesList.erase(applesList.begin());
        }

        // Add today's apples
        if (day < n && apples[day] > 0) {
            applesList.push_back({day + days[day], apples[day]});
        }

        // Try to eat an apple from the earliest expiring batch
        if (!applesList.empty()) {
            applesList.front().second--; // Eat one apple
            if (applesList.front().second == 0) {
                applesList.erase(applesList.begin());
            }
            totalEaten++;
        }

        day++; // Move to the next day
    }

    return totalEaten;
}
};

Maximum Number of Eaten Apples solution in Java:Optimal 
class Solution {
    public int eatenApples(int[] apples, int[] days) {
        int n = apples.length;
        // Each element in appleList is an int[] where:
        // [0] = expiry day, [1] = number of apples remaining
        List<int[]> appleList = new ArrayList<>();
        int totalEaten = 0;
        int day = 0;
        
        while (day < n || !appleList.isEmpty()) {
            // Remove any batches of apples that have expired
            while (!appleList.isEmpty() && appleList.get(0)[0] <= day) {
                appleList.remove(0);
            }
            
            // Add today's apples (if any)
            if (day < n && apples[day] > 0) {
                appleList.add(new int[]{day + days[day], apples[day]});
            }
            
            // Eat an apple from the batch that is currently first in the list
            if (!appleList.isEmpty()) {
                appleList.get(0)[1]--;  // Eat one apple
                if (appleList.get(0)[1] == 0) {
                    appleList.remove(0);
                }
                totalEaten++;
            }
            
            day++; // Move on to the next day
        }
        
        return totalEaten;
    }
}

Maximum Number of Eaten Apples solution in Python:Optimal 
from typing import List

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        n = len(apples)
        # List of tuples: (expiry_day, remaining_apples)
        apples_list = []
        total_eaten = 0
        day = 0
        
        while day < n or apples_list:
            # Remove rotten apples (those with expiry day <= current day)
            while apples_list and apples_list[0][0] <= day:
                apples_list.pop(0)
            
            # Add today's apples if any
            if day < n and apples[day] > 0:
                apples_list.append((day + days[day], apples[day]))
            
            # Eat one apple from the earliest expiring batch (at the front of the list)
            if apples_list:
                expiry, count = apples_list[0]
                count -= 1  # Eat one apple
                total_eaten += 1
                if count == 0:
                    apples_list.pop(0)
                else:
                    apples_list[0] = (expiry, count)
            
            day += 1
        
        return total_eaten

Maximum Number of Eaten Apples solution in Javascript:Optimal 
class Solution {
  eatenApples(apples, days) {
    const n = apples.length;
    // Each element is [expiry_day, remaining_apples]
    let appleList = [];
    let totalEaten = 0;
    let day = 0;
    
    while (day < n || appleList.length > 0) {
      // Remove rotten apples (those with expiry_day <= current day)
      while (appleList.length > 0 && appleList[0][0] <= day) {
        appleList.shift();
      }
      
      // Add today's apples if available
      if (day < n && apples[day] > 0) {
        appleList.push([day + days[day], apples[day]]);
      }
      
      // Eat one apple from the batch that expires earliest (front of the list)
      if (appleList.length > 0) {
        appleList[0][1]--; // Eat one apple
        totalEaten++;
        if (appleList[0][1] === 0) {
          appleList.shift();
        }
      }
      
      day++; // Move to the next day
    }
    
    return totalEaten;
  }
}

Maximum Number of Eaten Apples complexity analysis:Time Complexity O(n log n).

Let n be the number of days. The approach involves inserting, removing, and updating apples using a min-heap (priority queue).

Inserting Apples: O(n log n).

Each day, if apples are produced, an entry {expiry_day, apples[i]} is added.

Each insertion takes O(log n).

Over n days, total insertion cost is O(n log n).

Removing Rotten Apples: O(n log n).

Each day, expired apples are removed from the heap.

Each removal takes O(log n).

Over n days, total removal cost is O(n log n).

Eating an Apple: O(n log n).

Reducing the apple count is O(1), but if an entry becomes empty, it is removed, which takes O(log n).

In the worst case, this happens every day, total O(n log n).

Final Time Complexity

Total complexity is O(n log n), which is efficient for large values of n.

Maximum Number of Eaten Apples complexity analysis: Space Complexity O(n ).

Auxiliary Space Complexity

Min-Heap Storage:O(n).

The heap stores pairs (expiry_day, apples[i]).

In the worst case, all n days produce apples, and none expire before the end.

This means the heap can grow to a maximum size of O(n).

Additional Variables:O(1)

A few integer variables like day, totalEaten, and loop counters use O(1) space.

Total Space Complexity: O(n)

Heap stores at most n elements, leading to O(n) space usage.

Additional variables use O(1) space.

Final total space complexity: O(n) (dominant factor is the heap storage).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Similar Problems

Parallel Courses III

In "Parallel Courses III," you're given several courses, each with a specified duration, along with a list of prerequisite relationships. The goal is to determine the minimum time required to complete all courses when you can take multiple courses concurrently as long as their prerequisites are satisfied. The problem essentially requires you to compute the longest time path in a directed acyclic graph representing the courses and their dependencies.

Minimum Time to Complete All Tasks

This problem asks you to determine the minimum total time a computer needs to be turned on to complete a set of tasks. Each task has a specific duration it must run (which can be non-continuous) and must be executed within a given time window [start, end]. Since the computer can run an unlimited number of tasks concurrently, the challenge is to schedule the tasks optimally, ensuring the computer is only on when necessary to fulfill all required durations.