Assign Mice Holes

JavaView on GFG

Intuition

Assign n mice to n holes to minimize maximum distance. Sort both, match greedily.

Algorithm

1Sort mice positions and hole positions. Pair mice[i] with holes[i]. Answer = max(|mice[i]-holes[i]|).

Common Pitfalls

•Greedy: sorted pairing minimizes max distance. Proof by exchange argument.

Assign Mice Holes.java

Java

// Approach: Greedy. Sort both mice and hole positions.
// Pair i-th mouse with i-th hole; the answer is the maximum absolute difference.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    public int assignHole(int[] mices, int[] holes) {
        Arrays.sort(mices);
        Arrays.sort(holes);
        int ans = 0;
        for (int i = 0; i < holes.length; i++)
            ans = Math.max(ans, Math.abs(holes[i] - mices[i]));
            
        return ans;
    }
};

Was this solution helpful?