LeetCode 2604 - Minimum Time to Eat All Grains

The problem asks us to determine the minimum time needed for all hens to eat all grains when both hens and grains are located on a one-dimensional line.

leetcodehardarraytwo-pointersbinary-searchsorting

LeetCode Problem 2604

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to determine the minimum time needed for all hens to eat all grains when both hens and grains are located on a one-dimensional line. Each hen can move left or right by 1 unit per second and can eat multiple grains, but only when occupying the same position as the grain. All hens move simultaneously and independently. The goal is to find the smallest number of seconds required for all grains to be eaten if the hens are assigned optimally.

The inputs are two integer arrays: hens of size n representing the positions of the hens, and grains of size m representing the positions of the grains. The output is a single integer representing the minimum time required.

The constraints indicate that n and m can be up to 20,000 and positions can be very large (up to 10^9). This means brute-force simulations of movements per second are infeasible, and we must leverage sorting and optimized search techniques. Important edge cases include when hens outnumber grains, grains outnumber hens, or positions are extremely skewed, such as all grains being far from all hens.

Approaches

The brute-force approach would attempt to simulate each second, moving each hen optimally to the nearest uneaten grain until all grains are eaten. While this is conceptually correct, it is too slow due to large constraints, potentially taking O(m * n * maxDistance), which is unacceptable.

The key insight for an optimal approach is that we only need to determine the minimum time T such that each grain can be assigned to a hen within T seconds. Since hens can move simultaneously and independently, this problem reduces to a matching problem along a sorted line. Sorting both arrays and using binary search on the minimum time T, combined with a greedy assignment check, provides a feasible solution. For a candidate time T, we attempt to assign grains to hens in order: if a hen can reach the next grain within T seconds, we assign as many contiguous grains as possible before moving to the next hen.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * maxDistance) O(m + n) Simulate each second; infeasible for large input
Optimal O((n + m) log(maxPos)) O(1) Binary search on time with greedy assignment; scalable

Algorithm Walkthrough

  1. Sort the hens and grains arrays. Sorting ensures that we can assign grains to hens in order, minimizing total movement and making the greedy strategy optimal.
  2. Define a helper function canEatAllIn(time) that checks if all grains can be eaten within time seconds. Initialize a pointer for the current grain. For each hen, assign as many grains as possible to the hen such that the maximum movement needed does not exceed time.
  3. Binary search on time. Set low = 0 and high = max(grains) - min(hens) as the maximum possible distance a hen might need to travel. While low < high, check the middle value mid. If canEatAllIn(mid) is True, try smaller time (high = mid). Otherwise, increase time (low = mid + 1).
  4. Return low, which will be the minimum time such that all grains can be eaten.

Why it works: The algorithm works because sorting allows the greedy assignment to be optimal: each hen takes the next contiguous grains it can reach. Binary search ensures that we efficiently find the smallest possible T without simulating each second.

Python Solution

from typing import List

class Solution:
    def minimumTime(self, hens: List[int], grains: List[int]) -> int:
        hens.sort()
        grains.sort()
        
        def canEatAllIn(time: int) -> bool:
            grain_idx = 0
            for hen in hens:
                if grain_idx >= len(grains):
                    break
                left = grains[grain_idx]
                right = left
                # Assign as many grains as possible to this hen
                while grain_idx < len(grains) and abs(hens[0] - grains[grain_idx]) <= time:
                    grain_idx += 1
            return grain_idx == len(grains)
        
        # Correct greedy check
        def canEatAllIn(time: int) -> bool:
            i = 0
            j = 0
            while i < len(hens) and j < len(grains):
                hen_pos = hens[i]
                start = j
                # Find the furthest grain this hen can eat within 'time'
                while j < len(grains):
                    left = abs(hen_pos - grains[start])
                    right = abs(hen_pos - grains[j])
                    if min(left, right) + (right - left) > time:
                        break
                    j += 1
                i += 1
            return j == len(grains)
        
        left, right = 0, 10**10
        while left < right:
            mid = (left + right) // 2
            if canEatAllIn(mid):
                right = mid
            else:
                left = mid + 1
        return left

The implementation first sorts hens and grains. The canEatAllIn function iterates over hens and greedily assigns contiguous grains each hen can reach within a candidate time. Binary search then efficiently finds the minimum feasible time.

Go Solution

import (
    "sort"
)

func minimumTime(hens []int, grains []int) int {
    sort.Ints(hens)
    sort.Ints(grains)

    canEatAllIn := func(time int) bool {
        i, j := 0, 0
        for i < len(hens) && j < len(grains) {
            hen := hens[i]
            start := j
            for j < len(grains) {
                left := abs(hen - grains[start])
                right := abs(hen - grains[j])
                if min(left, right)+right-left > time {
                    break
                }
                j++
            }
            i++
        }
        return j == len(grains)
    }

    left, right := 0, int(1e10)
    for left < right {
        mid := (left + right) / 2
        if canEatAllIn(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go version mirrors the Python approach with slice operations and helper functions for abs and min. Go does not require explicit type hints and handles arrays and slices efficiently.

Worked Examples

Example 1: hens = [3,6,7], grains = [2,4,7,9]

Sorted: hens = [3,6,7], grains = [2,4,7,9]. Binary search checks candidate times. Time 2 is feasible:

Hen Assigned Grains Time needed
3 2, 4 2
6 7 1
7 9 2

Maximum time = 2. Output = 2.

Example 2: hens = [4,6,109,111,213,215], grains = [5,110,214]

Sorted: hens = [4,6,109,111,213,215], grains = [5,110,214]. Binary search finds time 1 feasible:

Hen Assigned Grains Time needed
4 5 1
109 110 1
213 214 1

Maximum time = 1. Output = 1.

Complexity Analysis

Measure Complexity Explanation
Time O((n + m) log(maxPos)) Sorting takes O(n log n + m log m), binary search up to log(maxPos), and greedy check O(n + m) per iteration
Space O(1) Only pointers and constants used, no extra significant space

The complexity is efficient due to binary search on time and greedy assignment, avoiding simulation of each second.

Test Cases

# Basic examples
assert Solution().minimumTime([3,6,7], [2,4,7,9]) == 2  # Example 1
assert Solution().minimumTime([4,6,109,111,213,215], [5,110,214]) == 1  # Example 2

# Edge cases
assert Solution().minimumTime([0], [0]) == 0  # Hen already on grain
assert Solution().minimumTime([0], [1000000000]) == 1000000000  # Far away
assert Solution().minimumTime([1,3], [2,4]) == 1  # Multiple hens and grains nearby
assert Solution().minimumTime([1,2,3], [10,20,30]) == 27  # Distributed hens and grains
assert Solution().minimumTime([1,2,