1705. Maximum Number of Eaten Apples LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1705. Maximum Number of Eaten Apples LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Eaten Apples problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Number of Eaten Apples solution in C++
Maximum Number of Eaten Apples solution in Java
Maximum Number of Eaten Apples solution in Python
Additional Resources

1705. Maximum Number of Eaten Apples LeetCode Solution image

Problem Statement of Maximum Number of Eaten Apples

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.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1705. Maximum Number of Eaten Apples LeetCode Solution in C++

class Solution {
 public:
  int eatenApples(vector<int>& apples, vector<int>& days) {
    const int n = apples.size();
    int ans = 0;
    using P = pair<int, int>;  // (the rotten day, the number of apples)
    priority_queue<P, vector<P>, greater<>> minHeap;

    for (int i = 0; i < n || !minHeap.empty(); ++i) {  // i := day
      // Remove the rotten apples.
      while (!minHeap.empty() && minHeap.top().first <= i)
        minHeap.pop();
      // Add today's apples.
      if (i < n && apples[i] > 0)
        minHeap.emplace(i + days[i], apples[i]);
      // Eat one apple today.
      if (!minHeap.empty()) {
        const auto [rottenDay, numApples] = minHeap.top();
        minHeap.pop();
        if (numApples > 1)
          minHeap.emplace(rottenDay, numApples - 1);
        ++ans;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1705. Maximum Number of Eaten Apples LeetCode Solution in Java

class Solution {
  public int eatenApples(int[] apples, int[] days) {
    final int n = apples.length;
    int ans = 0;
    // (the rotten day, the number of apples)
    Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));

    for (int i = 0; i < n || !minHeap.isEmpty(); ++i) {
      // Remove the rotten apples.
      while (!minHeap.isEmpty() && minHeap.peek().getKey() <= i)
        minHeap.poll();
      // Add today's apples.
      if (i < n && apples[i] > 0)
        minHeap.offer(new Pair<>(i + days[i], apples[i]));
      // Eat one apple today.
      if (!minHeap.isEmpty()) {
        final int rottenDay = minHeap.peek().getKey();
        final int numApples = minHeap.poll().getValue();
        if (numApples > 1)
          minHeap.offer(new Pair<>(rottenDay, numApples - 1));
        ++ans;
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

1705. Maximum Number of Eaten Apples LeetCode Solution in Python

class Solution:
  def eatenApples(self, apples: list[int], days: list[int]) -> int:
    n = len(apples)
    ans = 0
    minHeap = []  # (the rotten day, the number of apples)

    i = 0
    while i < n or minHeap:
      # Remove the rotten apples.
      while minHeap and minHeap[0][0] <= i:
        heapq.heappop(minHeap)
      # Add today's apples.
      if i < n and apples[i] > 0:
        heapq.heappush(minHeap, (i + days[i], apples[i]))
      # Eat one apple today.
      if minHeap:
        rottenDay, numApples = heapq.heappop(minHeap)
        if numApples > 1:
          heapq.heappush(minHeap, (rottenDay, numApples - 1))
        ans += 1
      i += 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents