Watch 2 video solutions for Minimum Time to Eat All Grains, a hard level problem involving Array, Two Pointers, Binary Search. This walkthrough by LetsCode has 589 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n hens and m grains on a line. You are given the initial positions of the hens and the grains in two integer arrays hens and grains of size n and m respectively.
Any hen can eat a grain if they are on the same position. The time taken for this is negligible. One hen can also eat multiple grains.
In 1 second, a hen can move right or left by 1 unit. The hens can move simultaneously and independently of each other.
Return the minimum time to eat all grains if the hens act optimally.
Example 1:
Input: hens = [3,6,7], grains = [2,4,7,9] Output: 2 Explanation: One of the ways hens eat all grains in 2 seconds is described below: - The first hen eats the grain at position 2 in 1 second. - The second hen eats the grain at position 4 in 2 seconds. - The third hen eats the grains at positions 7 and 9 in 2 seconds. So, the maximum time needed is 2. It can be proven that the hens cannot eat all grains before 2 seconds.
Example 2:
Input: hens = [4,6,109,111,213,215], grains = [5,110,214] Output: 1 Explanation: One of the ways hens eat all grains in 1 second is described below: - The first hen eats the grain at position 5 in 1 second. - The fourth hen eats the grain at position 110 in 1 second. - The sixth hen eats the grain at position 214 in 1 second. - The other hens do not move. So, the maximum time needed is 1.
Constraints:
1 <= hens.length, grains.length <= 2*1040 <= hens[i], grains[j] <= 109Problem Overview: You are given positions of hens and grains on a number line. Each hen can move left or right and eats grains it passes. The task is to compute the minimum time required for all grains to be eaten if hens move optimally.
Approach 1: Greedy Simulation (Brute Force) (Exponential / Very Slow)
A naive way is to simulate movements of hens and assign grains in different orders, trying every possible strategy to see which finishes earliest. Each hen could move left first or right first, and grains could be assigned in multiple combinations. This leads to a combinatorial explosion because the assignment of grains to hens grows rapidly as input size increases. Time complexity becomes exponential in the number of grains, with O(2^g) style exploration in the worst case, and space complexity O(g) for recursion or tracking assignments. This approach only helps understand the problem constraints but is not practical.
Approach 2: Sorting + Binary Search with Greedy Check (Optimal) (O((n + m) log R) time, O(1) space)
The key observation: instead of directly simulating movements, search for the minimum time T that allows all grains to be eaten. If you can verify whether all grains can be eaten within time T, then binary search can find the smallest valid time.
Start by sorting hens and grains using sorting. Then binary search over the answer (time). For each candidate time T, run a greedy feasibility check. Iterate through hens from left to right and try to assign as many grains as possible. Maintain a pointer to the next uneaten grain. For each hen, compute the furthest grain it can cover within time T. The hen may go left first or right first, so calculate the maximum reachable range considering both movement patterns.
The feasibility check uses a two pointers style scan over the sorted grains. Each grain is processed at most once, which keeps the check linear. Binary search over the time range multiplies this by log R, where R is the maximum coordinate distance.
Recommended for interviews: The sorting + binary search solution is the expected approach. It demonstrates strong understanding of greedy verification combined with binary search on the answer. Interviewers typically look for the insight that the minimum time can be searched rather than directly computed. Explaining why the greedy feasibility check works is usually the key discussion point.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation (Brute Force) | Exponential | O(g) | Conceptual understanding of grain assignments; not practical for real constraints |
| Sorting + Binary Search with Greedy Check | O((n + m) log R) | O(1) | Optimal solution when positions lie on a line and feasibility can be verified greedily |