Log inSign up
easyGeeksforGeeksNot Started

Assign Mice to Holes

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

There are N mice and N holes placed along a 1D coordinate line. Each hole can accommodate exactly 1 mouse. A mouse can move 1 unit of distance per minute to the left or right.

Find the minimum number of minutes after which all mice are inside a hole. That is, minimize the maximum distance traveled by any mouse: max(|mice[i] - holes[i]|) across all matches.

Example 1 · Example 1: Three Mice and Holes:

Input: mice = [4, -4, 2], holes = [4, 0, 5]
Output: 4
Explanation: Sorted mice: [-4, 2, 4]\nSorted holes: [0, 4, 5]\nMouse -4 -> Hole 0: distance = |-4 - 0| = 4\nMouse 2 -> Hole 4: distance = |2 - 4| = 2\nMouse 4 -> Hole 5: distance = |4 - 5| = 1\nMax distance = max(4, 2, 1) = 4.

Constraints:

  • 1 <= N <= 105
  • -109 <= mice[i], holes[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove the non-crossing property in 1D matching problems.
  • Understand why bottleneck matching on a line reduces to sorting.
  • Implement the greedy solution across all 4 programming languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Equal number of sources and destinations on a 1D line.
  • One-to-one matching constraint.
  • Minimizing the maximum cost/distance (bottleneck matching).

Algorithmic Decision Tree:

  • When items and slots lie on a 1D line and cost is |pos1 - pos2|, sort both and match by relative rank.

Connected Patterns:

Assign CookiesBoats to Save PeopleMinimum Absolute Difference in Array

1. Brute Force — Full Permutation Search

Intuition

Generate all possible assignments of mice to holes via backtracking or permutation algorithms. For each permutation, compute the maximum distance any mouse traveled. Return the minimum maximum distance.

When to apply: When N <= 8 for verification.

Algorithm

  1. Step 1: Generate all permutations of indices 0 to N-1 for holes.
  2. Step 2: For each permutation, calculate curMax = max(|mice[i] - holes[perm[i]]|).
  3. Step 3: Track min across all permutations.
  4. Step 4: Return global minimum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int miceToHoles(vector<int>& mice, vector<int>& holes) {
11 int n = mice.size();
12 vector<int> p(n);
13 for (int i = 0; i < n; ++i) p[i] = i;
14
15 int minMaxDist = 1e9;
16 do {
17 int curMax = 0;
18 for (int i = 0; i < n; ++i) {
19 curMax = max(curMax, abs(mice[i] - holes[p[i]]));
20 }
21 minMaxDist = min(minMaxDist, curMax);
22 } while (next_permutation(p.begin(), p.end()));
23
24 return minMaxDist;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> mice = {4, -4, 2};
31 vector<int> holes = {4, 0, 5};
32 cout << "Min time: " << sol.miceToHoles(mice, holes) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N! * N) — Generates all N! permutations and checks N pairs per permutation.
  • Space complexity: O(N) — Recursion stack and permutation storage of size N.

Why Brute Force Doesn't Scale:

With N = 105, N! is astronomical. Sorting in O(N log N) runs in ~20ms.

For N = 100,000: O(N log N) requires ~1.7 * 106 comparisons, executing in under 30ms.

2. Better — Binary Search on Answer

Intuition

Sort mice and holes. Binary search distance D in range [0, 2 * 109]. For a candidate D, check if every |mice[i] - holes[i]| <= D. If valid, try smaller D; else try larger D.

When to apply: When demonstrating binary search over monotonic answers.

Algorithm

  1. Step 1: Sort mice and holes in ascending order.
  2. Step 2: Low = 0, High = 2 * 109.
  3. Step 3: Mid = (low + high) / 2. Check if all |mice[i] - holes[i]| <= mid.
  4. Step 4: If valid, answer = mid, high = mid - 1; else low = mid + 1.
  5. Step 5: Return answer.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int miceToHoles(vector<int>& mice, vector<int>& holes) {
11 sort(mice.begin(), mice.end());
12 sort(holes.begin(), holes.end());
13
14 int n = mice.size();
15 int low = 0, high = 2e9;
16 int ans = high;
17
18 while (low <= high) {
19 int mid = low + (high - low) / 2;
20 bool possible = true;
21 for (int i = 0; i < n; ++i) {
22 if (abs(mice[i] - holes[i]) > mid) {
23 possible = false;
24 break;
25 }
26 }
27 if (possible) {
28 ans = mid;
29 high = mid - 1;
30 } else {
31 low = mid + 1;
32 }
33 }
34 return ans;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> mice = {4, -4, 2};
41 vector<int> holes = {4, 0, 5};
42 cout << "Min time: " << sol.miceToHoles(mice, holes) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N log N + N log(Range)) — Sorting takes O(N log N). Binary search runs ~31 iterations of O(N) verification.
  • Space complexity: O(1) auxiliary — No extra memory beyond variables.

3. Optimal — Sort Both Arrays and Direct 1-to-1 Match

Intuition

Sorting both coordinates naturally aligns relative order. Matching mouse i to hole i avoids any crossing of paths. By simple triangle inequality / non-crossing proof, uncrossing any two intersecting paths never increases the maximum distance. Thus, the greedy sorted pairing is provably optimal.

When to apply: Always for Assign Mice to Holes.

Algorithm

  1. Step 1: Sort mice in ascending order.
  2. Step 2: Sort holes in ascending order.
  3. Step 3: Initialize maxTime = 0.
  4. Step 4: Iterate i from 0 to N - 1: maxTime = max(maxTime, |mice[i] - holes[i]|).
  5. Step 5: Return maxTime.

Interactive Trace for Assign Mice to Holes

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compare mouse 0 at -4 with hole 0 at 0
Visual state
Values and pointers at this exact step
pointers
S
assigned
assigned
pending
pending
pending
pending
0
↑ mouse
1
↑ hole
2
3
4
5
Check / comparison
|-4 - 0| = 4
Decision / next transition
Assign mouse 0 to hole 0. maxTime = 4.
Why this step matters

Step 1: Compare mouse 0 at -4 with hole 0 at 0. Distance = |-4 - 0| = 4. maxTime = 4.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int miceToHoles(vector<int>& mice, vector<int>& holes) {
11 sort(mice.begin(), mice.end());
12 sort(holes.begin(), holes.end());
13
14 int maxTime = 0;
15 for (int i = 0; i < mice.size(); ++i) {
16 maxTime = max(maxTime, abs(mice[i] - holes[i]));
17 }
18 return maxTime;
19 }
20};
21
22int main() {
23 Solution sol;
24 vector<int> mice = {4, -4, 2};
25 vector<int> holes = {4, 0, 5};
26 cout << "Min time: " << sol.miceToHoles(mice, holes) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting two arrays of size N takes O(N log N). Linear scan takes O(N).
  • Space complexity: O(1) auxiliary — In-place sorting uses O(1) auxiliary space beyond standard sort stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All N! PermutationsO(N! * N)O(N) recursion stackGenerate all permutations of assigning holes to mice. For each permutation, calculate max(|mice[i] - holes[perm[i]]|). Return the minimum.N! permutation generation.
2.Better — Binary Search on Answer + Greedy / Bipartite MatchingO(N log(max_dist))O(1)Binary search on max distance D. For a given D, check if valid matching exists where |mice[i] - holes[i]| <= D after sorting.Binary search iterations.
3.Optimal — Sort Both Arrays and Direct 1-to-1 MatchOptimalO(N log N)O(1) auxiliarySort both mice and holes arrays. Compute max(|mice[i] - holes[i]|) in a single linear pass.Initial sorting.

Common Pitfalls & Crucial Edge Cases

Matching without sorting

Pairing mice in arbitrary order can produce crossed paths that drastically inflate the maximum distance.

Summing distances instead of finding maximum

The problem asks for the time when the LAST mouse finishes (min-max), not total distance.

Crucial Edge Cases to Validate:

  • N = 1 — Absolute difference |mice[0] - holes[0]| is directly returned.
  • All mice and holes at identical positions — Returns 0.
  • Negative coordinates — Absolute difference abs() handles negative numbers correctly.
  • Duplicate positions — Multiple mice or holes at identical locations handled naturally by sorting.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the non-crossing property: 'If paths cross, swapping targets cannot increase the maximum distance.'
  2. Notice that the problem asks for min-max (bottleneck matching), which simplifies to monotonic greedy matching on 1D lines.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is crossing paths in 1D matching never better than uncrossed matching?

Back to DSA Sheet