Problem

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 theminimum time to eat all grains if the hens act optimally.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5
6
7
8
9

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*104
  • 0 <= hens[i], grains[j] <= 10^9

Solution

Method 1 – Binary Search + Two Pointers

Intuition

The minimum time is the smallest t such that all grains can be assigned to hens, with each hen able to reach all its assigned grains within t seconds. We can use binary search on t and check feasibility using a greedy two-pointer approach.

Approach

  1. Sort hens and grains.
  2. Binary search for the minimum t (from 0 to max distance).
  3. For each t, use two pointers:
    • For each hen, assign as many grains as possible within t seconds.
    • Move to next hen when current can’t reach next grain within t.
  4. If all grains are assigned, t is feasible.
  5. Return the smallest feasible t.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int minimumTime(vector<int>& hens, vector<int>& grains) {
        sort(hens.begin(), hens.end());
        sort(grains.begin(), grains.end());
        int left = 0, right = 1e9, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int i = 0, j = 0, n = hens.size(), m = grains.size();
            while (i < n && j < m) {
                int start = j;
                while (j < m && abs(grains[j] - hens[i]) <= mid) ++j;
                if (start == j) ++i;
            }
            if (j == m) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func minimumTime(hens, grains []int) int {
    sort.Ints(hens)
    sort.Ints(grains)
    left, right, ans := 0, 1e9, -1
    for left <= right {
        mid := (left + right) / 2
        i, j := 0, 0
        for i < len(hens) && j < len(grains) {
            start := j
            for j < len(grains) && abs(grains[j]-hens[i]) <= mid {
                j++
            }
            if start == j {
                i++
            }
        }
        if j == len(grains) {
            ans = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return ans
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int minimumTime(int[] hens, int[] grains) {
        Arrays.sort(hens);
        Arrays.sort(grains);
        int left = 0, right = (int)1e9, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int i = 0, j = 0, n = hens.length, m = grains.length;
            while (i < n && j < m) {
                int start = j;
                while (j < m && Math.abs(grains[j] - hens[i]) <= mid) ++j;
                if (start == j) ++i;
            }
            if (j == m) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun minimumTime(hens: IntArray, grains: IntArray): Int {
        hens.sort()
        grains.sort()
        var left = 0
        var right = 1_000_000_000
        var ans = -1
        while (left <= right) {
            val mid = left + (right - left) / 2
            var i = 0
            var j = 0
            while (i < hens.size && j < grains.size) {
                val start = j
                while (j < grains.size && kotlin.math.abs(grains[j] - hens[i]) <= mid) j++
                if (start == j) i++
            }
            if (j == grains.size) {
                ans = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minimumTime(self, hens: list[int], grains: list[int]) -> int:
        hens.sort()
        grains.sort()
        left, right, ans = 0, 10**9, -1
        while left <= right:
            mid = (left + right) // 2
            i, j = 0, 0
            while i < len(hens) and j < len(grains):
                start = j
                while j < len(grains) and abs(grains[j] - hens[i]) <= mid:
                    j += 1
                if start == j:
                    i += 1
            if j == len(grains):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn minimum_time(mut hens: Vec<i32>, mut grains: Vec<i32>) -> i32 {
        hens.sort();
        grains.sort();
        let (mut left, mut right, mut ans) = (0, 1_000_000_000, -1);
        while left <= right {
            let mid = left + (right - left) / 2;
            let (mut i, mut j) = (0, 0);
            while i < hens.len() && j < grains.len() {
                let start = j;
                while j < grains.len() && (grains[j] - hens[i]).abs() <= mid {
                    j += 1;
                }
                if start == j {
                    i += 1;
                }
            }
            if j == grains.len() {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    minimumTime(hens: number[], grains: number[]): number {
        hens.sort((a, b) => a - b);
        grains.sort((a, b) => a - b);
        let left = 0, right = 1e9, ans = -1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            let i = 0, j = 0;
            while (i < hens.length && j < grains.length) {
                const start = j;
                while (j < grains.length && Math.abs(grains[j] - hens[i]) <= mid) j++;
                if (start === j) i++;
            }
            if (j === grains.length) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O((n + m) log D), where n = hens.length, m = grains.length, D = max position difference.
  • 🧺 Space complexity: O(1), only pointers and counters are used.