LeetCode 1705 - Maximum Number of Eaten Apples

LeetCode Problem 1705

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem describes a scenario with a series of apple trees that grow apples for n consecutive days. Each day, the tree produces a number of apples given by apples[i], and these apples have a limited lifespan, given by days[i]. An apple that grows on day i will rot after days[i] days, which means it becomes inedible on day i + days[i]. Some days may have zero apples, represented by apples[i] = 0 and days[i] = 0. You can eat at most one apple per day, but you are allowed to continue eating apples after the n-day growth period if any remain unspoiled.

The inputs are two arrays of equal length n, where 1 <= n <= 20,000 and apple counts and expiration days can be up to 20,000. This tells us that a brute-force approach iterating over every possible combination of apples and days will likely be too slow.

The expected output is a single integer representing the maximum number of apples you can eat under these constraints. Edge cases to consider include days when no apples grow, days when all apples rot before you can eat them, and days when multiple batches of apples with different expiration dates exist simultaneously. The problem guarantees that days[i] = 0 only occurs when apples[i] = 0, so we do not need to handle inconsistent input.

Approaches

The brute-force approach would involve iterating day by day and checking all apples grown so far to find a non-rotten apple to eat. For each day, you would scan the list of apples collected so far, remove rotten ones, and choose one to eat. This approach is correct because it simulates the eating process accurately. However, it is too slow for large inputs because on each day you may check up to O(n) apples, giving an overall complexity of O(n^2).

The key observation for an optimal approach is that you always want to eat the apple that will rot the soonest to maximize the total number eaten. This is a classic greedy strategy. By maintaining a min-heap (priority queue) keyed by the expiration day of each apple batch, you can efficiently track the batch that must be consumed first. On each day, you remove expired apples, add new apples, and eat from the batch with the earliest expiration date. This reduces the complexity from O(n^2) to O(n log n) because heap operations take logarithmic time.

Algorithm Walkthrough

1. Initialize a min-heap to store tuples of (expiration_day, apple_count).
2. Initialize a counter total_eaten to 0.
3. Iterate through each day i from 0 to n-1.
4. Remove all apple batches from the heap whose expiration day is less than or equal to the current day, because they are rotten.
5. If apples[i] > 0, push (i + days[i], apples[i]) onto the heap to represent the new apples and their expiration day.
6. If the heap is not empty after cleanup, pop the batch with the earliest expiration date and eat one apple from it. If there are remaining apples in the batch, push it back with one fewer apple.
7. Increment total_eaten each time an apple is eaten.
8. Continue iterating beyond day n-1 if the heap is not empty, simulating the consumption of remaining apples until all have rotted.

Why it works: By always consuming the apple with the earliest expiration date, you ensure that no apple is wasted unnecessarily. This greedy strategy guarantees the maximum number of apples eaten because delaying consumption of an apple that would rot soon could prevent you from eating that apple at all.

Python Solution

from typing import List
import heapq

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        min_heap = []
        total_eaten = 0
        n = len(apples)
        day = 0
        
        while day < n or min_heap:
            if day < n and apples[day] > 0:
                heapq.heappush(min_heap, (day + days[day], apples[day]))
            
            while min_heap and min_heap[0][0] <= day:
                heapq.heappop(min_heap)
            
            if min_heap:
                exp_day, count = heapq.heappop(min_heap)
                if count > 1:
                    heapq.heappush(min_heap, (exp_day, count - 1))
                total_eaten += 1
            
            day += 1
        
        return total_eaten

This implementation first initializes a min-heap and day counter. For each day, it adds new apples to the heap, removes rotten apples, and consumes one apple from the earliest expiring batch. The loop continues beyond the n days to eat remaining unspoiled apples. The heap ensures that operations like finding and removing the soonest-to-rot apple are efficient.

Go Solution

package main

import (
    "container/heap"
)

type AppleBatch struct {
    expDay int
    count  int
}

type MinHeap []AppleBatch

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].expDay < h[j].expDay }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(AppleBatch))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}

func eatenApples(apples []int, days []int) int {
    h := &MinHeap{}
    heap.Init(h)
    totalEaten := 0
    n := len(apples)
    day := 0

    for day < n || h.Len() > 0 {
        if day < n && apples[day] > 0 {
            heap.Push(h, AppleBatch{expDay: day + days[day], count: apples[day]})
        }

        for h.Len() > 0 && (*h)[0].expDay <= day {
            heap.Pop(h)
        }

        if h.Len() > 0 {
            batch := heap.Pop(h).(AppleBatch)
            if batch.count > 1 {
                heap.Push(h, AppleBatch{expDay: batch.expDay, count: batch.count - 1})
            }
            totalEaten++
        }

        day++
    }

    return totalEaten
}

The Go implementation mirrors the Python logic, using a custom min-heap type for AppleBatch. The main differences involve handling heap operations with Go's container/heap interface and struct types.

Worked Examples

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

Example 2: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]