2604. Minimum Time to Eat All Grains 🔒

HardArrayTwo PointersBinary SearchSorting

Problem Description

You have n hens and m grains positioned on a number line. The initial positions of the hens are given in an integer array hens of size n, and the positions of the grains are given in an integer array grains of size m.

A hen can eat a grain if they are at the same position, and eating takes no time. Each hen can eat multiple grains.

In each second, a hen can move either left or right by 1 unit. All hens can move simultaneously and independently of each other.

Your task is to find the minimum time required for the hens to eat all the grains if they move optimally.

For example, if a hen is at position 5 and there are grains at positions 3 and 7, the hen could move left to position 3 (taking 2 seconds) to eat that grain, then move right to position 7 (taking 4 seconds) to eat the other grain, for a total of 6 seconds. However, if another hen helps, the time could be reduced.

The goal is to coordinate all hens' movements to minimize the maximum time any hen needs to travel to ensure all grains are consumed.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that if we can eat all grains within time t, then we can definitely eat all grains within any time greater than t. This monotonic property suggests using binary search on the answer.

Think about it this way: if we fix a time limit t, we can check whether it's possible for the hens to eat all grains within this time. Each hen has a "reachable range" - the set of positions it can visit within t seconds. The question becomes: can we assign grains to hens such that each grain falls within some hen's reachable range?

To make this assignment optimal, we should process hens and grains in sorted order from left to right. Why? Because if a hen on the left skips a grain to go further right, a hen on the right would need to come back left to eat that skipped grain, which is inefficient.

For each hen at position x with time budget t, it can reach any position in the range [x - t, x + t]. However, the hen might need to eat multiple grains, so its movement pattern matters. If a hen needs to eat grains on both sides of its starting position, it has two strategies:

Go left first, eat grains, then go right
Go right first, eat grains, then go left

The optimal choice depends on the grain positions. If the hen goes left by distance d first, then returns and goes right, the total distance for reaching a grain at position y (where y > x) would be d + (y - x) + d = 2d + (y - x). The hen should eat all grains where this total distance is within t.

By sorting both arrays and using a greedy approach where each hen eats as many grains as possible from left to right within its time budget, we can efficiently check if a given time t is sufficient. Binary search then finds the minimum such t.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

First, we sort both the hens and grains arrays by position from left to right. This allows us to process them in order and apply a greedy strategy.

We use binary search to find the minimum time t. The search range is from 0 to a reasonable upper bound (calculated as the distance from the first hen to the first grain plus the span of all grains).

The core of the solution is the check(t) function that determines if all grains can be eaten within time t:

Initialize a pointer j = 0 to track the leftmost uneaten grain.
For each hen at position x, we determine which grains it can eat:
- Case 1: Grain is to the left (y ≤ x)
  - Calculate distance d = x - y
  - If d > t, this grain cannot be reached, return false
  - Move pointer j right to skip all grains at or left of the hen's position (these are easy to eat on the way)
  - Continue moving j right while the hen can still reach grains to its right. The hen can reach grain at position grains[j] if:
    - Going left first then right: d + (grains[j] - y) ≤ t
    - Going right first then back: (grains[j] - x) + (grains[j] - y) ≤ t
    - We use: min(d, grains[j] - x) + grains[j] - y ≤ t
- Case 2: Grain is to the right (y > x)
  - Simply move j right while grains[j] - x ≤ t
  - The hen just needs to move right to eat these grains
After processing all hens, check if j == m (all grains eaten). If yes, time t is sufficient.

The binary search finds the minimum t where check(t) returns true. We use bisect_left with a key function to efficiently find this minimum time.

The time complexity is O((n + m) log(n + m) + (n + m) log R) where R is the search range, due to sorting and binary search with linear checking.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

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

Step 1: Sort both arrays (already sorted in this case)

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

Step 2: Binary search for minimum time

The search range is from 0 to approximately 210 (distance from first hen to first grain plus grain span).

Let's check if t = 3 seconds is sufficient:

Check function with t = 3:

Start with grain pointer j = 0 (grain at position 5)

Hen 1 at position 4:

First grain is at position 5 (to the right)
Distance = 5 - 4 = 1 ≤ 3 ✓
Hen can reach it, move j to 1
Check next grain at 110: distance = 110 - 4 = 106 > 3 ✗
Hen 1 eats grain at position 5

Hen 2 at position 6:

Current grain is at position 110 (to the right)
Distance = 110 - 6 = 104 > 3 ✗
Hen 2 can't reach any remaining grains

Hen 3 at position 109:

Current grain is at position 110 (to the right)
Distance = 110 - 109 = 1 ≤ 3 ✓
Hen can reach it, move j to 2
Check next grain at 214: distance = 214 - 109 = 105 > 3 ✗
Hen 3 eats grain at position 110

Hen 4 at position 111:

Current grain is at position 214 (to the right)
Distance = 214 - 111 = 103 > 3 ✗
Hen 4 can't reach any remaining grains

Hen 5 at position 213:

Current grain is at position 214 (to the right)
Distance = 214 - 213 = 1 ≤ 3 ✓
Hen can reach it, move j to 3
All grains consumed! (j = 3 = m)

Result: t = 3 is sufficient. Through binary search, we'd find that 3 is actually the minimum time needed.

Why this works:

Hen 1 moves right 1 unit to eat grain at 5
Hen 3 moves right 1 unit to eat grain at 110
Hen 5 moves right 1 unit to eat grain at 214
Maximum time any hen travels: 1 second

Each hen efficiently handles grains in its vicinity, and the greedy left-to-right assignment ensures no grain is left behind.

Solution Implementation

1class Solution:
2    def minimumTime(self, hens: List[int], grains: List[int]) -> int:
3        def can_eat_all_grains_in_time(time_limit):
4            """
5            Check if all grains can be eaten within the given time limit.
6            Each hen moves optimally to cover grains.
7            """
8            grain_index = 0
9            num_grains = len(grains)
10          
11            for hen_position in hens:
12                # All grains have been covered
13                if grain_index == num_grains:
14                    return True
15              
16                current_grain_position = grains[grain_index]
17              
18                if current_grain_position <= hen_position:
19                    # Grain is to the left of or at hen's position
20                    distance_to_left = hen_position - current_grain_position
21                  
22                    # Can't reach this grain in time
23                    if distance_to_left > time_limit:
24                        return False
25                  
26                    # Eat all grains to the left within reach
27                    while grain_index < num_grains and grains[grain_index] <= hen_position:
28                        grain_index += 1
29                  
30                    # After going left, hen can also go right
31                    # Two strategies: go left first then right, or go right first then left
32                    # Take the better option that covers more grains
33                    while grain_index < num_grains:
34                        right_distance = grains[grain_index] - hen_position
35                        total_distance = min(distance_to_left, right_distance) + grains[grain_index] - current_grain_position
36                        if total_distance <= time_limit:
37                            grain_index += 1
38                        else:
39                            break
40                else:
41                    # Grain is to the right of hen's position
42                    # Hen only needs to move right
43                    while grain_index < num_grains and grains[grain_index] - hen_position <= time_limit:
44                        grain_index += 1
45          
46            # Check if all grains have been covered
47            return grain_index == num_grains
48      
49        # Sort positions for greedy algorithm
50        hens.sort()
51        grains.sort()
52      
53        # Set upper bound for binary search
54        # Worst case: first hen goes to first grain, then to last grain
55        max_possible_time = abs(hens[0] - grains[0]) + grains[-1] - grains[0] + 1
56      
57        # Binary search for minimum time where all grains can be eaten
58        return bisect_left(range(max_possible_time), True, key=can_eat_all_grains_in_time)
59

1class Solution {
2    private int[] hens;
3    private int[] grains;
4    private int totalGrains;
5
6    /**
7     * Finds the minimum time for all hens to eat all grains.
8     * Uses binary search to find the minimum time where all grains can be consumed.
9     * 
10     * @param hens array of hen positions
11     * @param grains array of grain positions
12     * @return minimum time needed for all grains to be eaten
13     */
14    public int minimumTime(int[] hens, int[] grains) {
15        this.totalGrains = grains.length;
16        this.hens = hens;
17        this.grains = grains;
18      
19        // Sort both arrays to process them in order
20        Arrays.sort(hens);
21        Arrays.sort(grains);
22      
23        // Binary search bounds: minimum is 0, maximum is the distance from first hen to first grain
24        // plus the span of all grains
25        int left = 0;
26        int right = Math.abs(hens[0] - grains[0]) + grains[totalGrains - 1] - grains[0];
27      
28        // Binary search for minimum time
29        while (left < right) {
30            int mid = (left + right) >> 1;  // Equivalent to (left + right) / 2
31          
32            if (canEatAllGrains(mid)) {
33                // If possible with mid time, try smaller time
34                right = mid;
35            } else {
36                // If not possible, need more time
37                left = mid + 1;
38            }
39        }
40      
41        return left;
42    }
43
44    /**
45     * Checks if all grains can be eaten within the given time limit.
46     * Each hen moves optimally to eat as many grains as possible.
47     * 
48     * @param timeLimit the time limit to check
49     * @return true if all grains can be eaten within timeLimit, false otherwise
50     */
51    private boolean canEatAllGrains(int timeLimit) {
52        int grainIndex = 0;
53      
54        // Process each hen from left to right
55        for (int henPosition : hens) {
56            // All grains have been assigned
57            if (grainIndex == totalGrains) {
58                return true;
59            }
60          
61            int firstGrainPosition = grains[grainIndex];
62          
63            if (firstGrainPosition <= henPosition) {
64                // Grain is to the left of or at hen's position
65                int distanceToLeft = henPosition - firstGrainPosition;
66              
67                // If the leftmost grain is too far, this hen can't reach it
68                if (distanceToLeft > timeLimit) {
69                    return false;
70                }
71              
72                // Eat all grains to the left that are within reach
73                while (grainIndex < totalGrains && grains[grainIndex] <= henPosition) {
74                    grainIndex++;
75                }
76              
77                // After eating left grains, try to eat grains to the right
78                // The hen can go left first then right, optimizing the path
79                while (grainIndex < totalGrains && 
80                       Math.min(distanceToLeft, grains[grainIndex] - henPosition) + 
81                       grains[grainIndex] - firstGrainPosition <= timeLimit) {
82                    grainIndex++;
83                }
84            } else {
85                // All reachable grains are to the right of hen's position
86                while (grainIndex < totalGrains && 
87                       grains[grainIndex] - henPosition <= timeLimit) {
88                    grainIndex++;
89                }
90            }
91        }
92      
93        // Check if all grains have been eaten
94        return grainIndex == totalGrains;
95    }
96}
97

1class Solution {
2public:
3    int minimumTime(vector<int>& hens, vector<int>& grains) {
4        int numGrains = grains.size();
5      
6        // Sort both arrays to process them in order
7        sort(hens.begin(), hens.end());
8        sort(grains.begin(), grains.end());
9      
10        // Binary search bounds: minimum time is 0, maximum is the worst case scenario
11        // where first hen needs to go to first grain then traverse to last grain
12        int left = 0;
13        int right = abs(hens[0] - grains[0]) + grains[numGrains - 1] - grains[0];
14      
15        // Lambda function to check if all grains can be eaten within given time
16        auto canEatAllGrains = [&](int timeLimit) -> bool {
17            int grainIndex = 0;
18          
19            // For each hen, determine which grains it can eat within the time limit
20            for (int henPosition : hens) {
21                // All grains have been assigned
22                if (grainIndex == numGrains) {
23                    return true;
24                }
25              
26                int firstGrainPosition = grains[grainIndex];
27              
28                if (firstGrainPosition <= henPosition) {
29                    // Case 1: First unassigned grain is to the left of hen
30                    int distanceToLeft = henPosition - firstGrainPosition;
31                  
32                    // If hen cannot reach the leftmost grain in time
33                    if (distanceToLeft > timeLimit) {
34                        return false;
35                    }
36                  
37                    // Skip all grains to the left of hen (hen can reach them by going left)
38                    while (grainIndex < numGrains && grains[grainIndex] <= henPosition) {
39                        ++grainIndex;
40                    }
41                  
42                    // Try to cover grains to the right as well
43                    // Hen can go left first then right, minimizing backtracking
44                    while (grainIndex < numGrains && 
45                           min(distanceToLeft, grains[grainIndex] - henPosition) + 
46                           grains[grainIndex] - firstGrainPosition <= timeLimit) {
47                        ++grainIndex;
48                    }
49                } else {
50                    // Case 2: All unassigned grains are to the right of hen
51                    // Hen only needs to move right
52                    while (grainIndex < numGrains && 
53                           grains[grainIndex] - henPosition <= timeLimit) {
54                        ++grainIndex;
55                    }
56                }
57            }
58          
59            // Check if all grains have been assigned to hens
60            return grainIndex == numGrains;
61        };
62      
63        // Binary search for the minimum time needed
64        while (left < right) {
65            int mid = (left + right) >> 1;  // Equivalent to (left + right) / 2
66          
67            if (canEatAllGrains(mid)) {
68                // If possible with mid time, try to find a smaller time
69                right = mid;
70            } else {
71                // If not possible with mid time, need more time
72                left = mid + 1;
73            }
74        }
75      
76        return left;
77    }
78};
79

1/**
2 * Finds the minimum time required for all hens to eat all grains
3 * @param hens - Array of hen positions
4 * @param grains - Array of grain positions
5 * @returns Minimum time for all grains to be eaten
6 */
7function minimumTime(hens: number[], grains: number[]): number {
8    // Sort both arrays to process positions from left to right
9    hens.sort((a, b) => a - b);
10    grains.sort((a, b) => a - b);
11  
12    const grainsCount = grains.length;
13  
14    // Binary search bounds for the minimum time
15    let left = 0;
16    // Upper bound: worst case scenario where first hen needs to cover all grains
17    let right = Math.abs(hens[0] - grains[0]) + grains[grainsCount - 1] - grains[0] + 1;
18
19    /**
20     * Checks if all grains can be eaten within given time limit
21     * @param timeLimit - Maximum time allowed for hens to eat grains
22     * @returns True if all grains can be eaten within time limit
23     */
24    const canEatAllGrains = (timeLimit: number): boolean => {
25        let grainIndex = 0;
26      
27        // Process each hen from left to right
28        for (const henPosition of hens) {
29            // All grains have been assigned
30            if (grainIndex === grainsCount) {
31                return true;
32            }
33          
34            const currentGrainPosition = grains[grainIndex];
35          
36            // Case 1: Current grain is to the left of or at hen's position
37            if (currentGrainPosition <= henPosition) {
38                const distanceToLeft = henPosition - currentGrainPosition;
39              
40                // Hen cannot reach this grain within time limit
41                if (distanceToLeft > timeLimit) {
42                    return false;
43                }
44              
45                // Skip all grains to the left of hen that are already covered
46                while (grainIndex < grainsCount && grains[grainIndex] <= henPosition) {
47                    grainIndex++;
48                }
49              
50                // Hen can go left first, then return and go right
51                // Check how many grains to the right can be covered
52                while (grainIndex < grainsCount && 
53                       Math.min(distanceToLeft, grains[grainIndex] - henPosition) + 
54                       grains[grainIndex] - currentGrainPosition <= timeLimit) {
55                    grainIndex++;
56                }
57            } 
58            // Case 2: Current grain is to the right of hen's position
59            else {
60                // Hen only needs to go right, cover as many grains as possible
61                while (grainIndex < grainsCount && 
62                       grains[grainIndex] - henPosition <= timeLimit) {
63                    grainIndex++;
64                }
65            }
66        }
67      
68        // Check if all grains have been covered
69        return grainIndex === grainsCount;
70    };
71
72    // Binary search for the minimum time
73    while (left < right) {
74        const mid = (left + right) >> 1;  // Equivalent to Math.floor((left + right) / 2)
75      
76        if (canEatAllGrains(mid)) {
77            // If possible with mid time, try smaller time
78            right = mid;
79        } else {
80            // If not possible with mid time, need more time
81            left = mid + 1;
82        }
83    }
84  
85    return left;
86}
87

Time and Space Complexity

Time Complexity: O(n × log n + m × log m + (m + n) × log U)

The time complexity breaks down as follows:

O(n × log n) for sorting the hens array where n is the number of hens
O(m × log m) for sorting the grains array where m is the number of grains
The binary search using bisect_left runs in O(log r) iterations where r represents the search range
The value of r is bounded by abs(hens[0] - grains[0]) + grains[-1] - grains[0] + 1, which is O(U) where U is the maximum value among all hen and grain positions
For each binary search iteration, the check function is called, which runs in O(m + n) time:
- The outer loop iterates through all n hens
- The inner while loops collectively traverse the m grains at most once per check call due to the monotonic movement of index j
Therefore, the binary search contributes O((m + n) × log U) to the total complexity

Space Complexity: O(log m + log n)

The space complexity comes from:

O(log n) for the sorting algorithm's recursion stack when sorting the hens array
O(log m) for the sorting algorithm's recursion stack when sorting the grains array
O(1) for the variables used in the check function and main logic
The sorting operations use in-place algorithms (like Timsort in Python), which require logarithmic extra space for the recursion stack

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Calculation of Maximum Coverage When Hen Goes Left First

The Pitfall: When a hen encounters grains to its left, it needs to decide how far right it can go after eating the leftmost grain. The code calculates the total distance as:

total_distance = min(distance_to_left, right_distance) + grains[grain_index] - current_grain_position

This formula assumes the hen can optimize between two strategies:

Go left first, then right: distance = distance_to_left + (right_grain - left_grain)
Go right first, then left: distance = 2 * right_distance + distance_to_left

However, the implementation doesn't correctly represent the second strategy. The actual distance for going right first should be 2 * right_distance + distance_to_left, not what's calculated.

The Solution: Replace the distance calculation with the correct formula:

# Strategy 1: Go left first, then right
left_first = distance_to_left + (grains[grain_index] - current_grain_position)
# Strategy 2: Go right first, then back left
right_first = 2 * (grains[grain_index] - hen_position) + distance_to_left
# Take minimum of both strategies
total_distance = min(left_first, right_first)

2. Not Handling Edge Cases with Empty Arrays

The Pitfall: The code doesn't explicitly handle edge cases where either hens or grains arrays might be empty. Accessing hens[0] or grains[0] would raise an IndexError.

The Solution: Add edge case handling at the beginning:

if not grains:  # No grains to eat
    return 0
if not hens:  # No hens to eat grains (shouldn't happen based on problem)
    return float('inf')

3. Potential Integer Overflow in Upper Bound Calculation

The Pitfall: The upper bound calculation might be too conservative or potentially overflow for very large position values:

max_possible_time = abs(hens[0] - grains[0]) + grains[-1] - grains[0] + 1

The Solution: Use a more robust upper bound that considers the maximum possible distance any hen might need to travel:

# Maximum distance would be from leftmost position to rightmost position
all_positions = hens + grains
max_possible_time = max(all_positions) - min(all_positions)

4. Inefficient Binary Search Implementation

The Pitfall: Using bisect_left with a range object and key function creates unnecessary overhead and might not be intuitive for all edge cases.

The Solution: Implement a standard binary search for clarity and efficiency:

left, right = 0, max_possible_time
while left < right:
    mid = (left + right) // 2
    if can_eat_all_grains_in_time(mid):
        right = mid
    else:
        left = mid + 1
return left

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know