Problem

There are N mice and N holes are placed in a straight line. Each hole can accommodate only 1 mouse. A mouse can stay at his position, move one step right from x to x + 1, or move one step left from x to x − 1. Any of these moves consumes 1 minute. Assign mice to holes so that the time when the last mouse gets inside a hole is minimized(i.e., minimize the maximum time taken by any mouse).

Input

  • A: List of positions of mice (length N)
  • B: List of positions of holes (length N)

Output

  • Single integer: the minimum time when the last mouse gets inside a hole

Note: The final answer will fit in a 32-bit signed integer.

Examples

Example 1

1
2
3
4
5
6
7
8

 A = [4, -4, 2]
 B = [4, 0, 5]
Assignment:
- Mouse at 4 → Hole at 4: 0 minutes
- Mouse at -4 → Hole at 0: 4 minutes
- Mouse at 2 → Hole at 5: 3 minutes

All mice are in holes after 4 minutes. No better assignment is possible, so the answer is **4**.

Solution

Method 1 - Greedy Matching

This is a greedy matching problem. To minimize the maximum time, sort both the mice and holes positions. Assign the ith mouse to the ith hole. The answer is the maximum absolute difference between the positions of each assigned pair.

Why does this work? Sorting ensures that the largest gaps are minimized, and no better assignment can improve the maximum distance for any mouse.

Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
	// A - mice; B - holes
	public int mice(ArrayList<Integer> A, ArrayList<Integer> B) {
		if (A.size() != B.size()) {
			return -1;
		}
		Collections.sort(A);
		Collections.sort(B);
		int max = 0;
		for (int i = 0; i < A.size(); i++) {
			max = Math.max(max, Math.abs(A.get(i) - B.get(i)));
		}
		return max;
	}
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
	def mice(self, mice, holes):
		if len(mice) != len(holes):
			return -1
		mice.sort()
		holes.sort()
		max_time = 0
		for m, h in zip(mice, holes):
			max_time = max(max_time, abs(m - h))
		return max_time

Complexity

  • ⏰ Time complexity: O(N log N) — Sorting both arrays takes O(N log N), and the final loop is O(N).
  • 🧺 Space complexity: O(1) — Sorting can be done in-place; only a few variables are used.