Problem

Consider the following scenario: there are N mice and N holes placed at integer points along a line. Given this, find a method that maps mice to holes such that the largest number of steps any mouse takes is minimized.

Each move consists of moving one mouse one unit to the left or right, and only one mouse can fit inside each hole.

For example, suppose the mice are positioned at [1, 4, 9, 15], and the holes are located at [10, -5, 0, 16]. In this case, the best pairing would require us to send the mouse at 1 to the hole at -5, so our function should return 6.

Examples

Example 1

1
2
3
4
5
6

Input: mice = [1, 4, 9, 15], holes = [10, -5, 0, 16]
Output: 6
Explanation: 
After sorting: mice = [1, 4, 9, 15], holes = [-5, 0, 10, 16]
Best assignment: 1→-5 (6 steps), 4→0 (4 steps), 9→10 (1 step), 15→16 (1 step)
Maximum distance is 6.

Example 2

1
2
3
4
5
6

Input: mice = [4, -4, 2], holes = [4, 0, 5]
Output: 4
Explanation:
After sorting: mice = [-4, 2, 4], holes = [0, 4, 5]
Best assignment: -4→0 (4 steps), 2→4 (2 steps), 4→5 (1 step)
Maximum distance is 4.

Example 3

1
2
3
4
5

Input: mice = [1, 1, 1], holes = [2, 2, 2]
Output: 1
Explanation:
All mice at position 1, all holes at position 2.
Each mouse needs 1 step to reach any hole.

Example 4

1
2
3
4

Input: mice = [1], holes = [10]
Output: 9
Explanation:
Single mouse at 1, single hole at 10. Distance is 9.

Example 5

1
2
3
4
5
6
7
8

Input: mice = [7, 9, 8, 6, 2], holes = [9, 8, 8, 6, 2]
Output: 2
Explanation:
After sorting: mice = [2, 6, 7, 8, 9], holes = [2, 6, 8, 8, 9]
Best assignment: 2→2 (0), 6→6 (0), 7→8 (1), 8→8 (0), 9→9 (0)
Maximum distance is 1. Wait, let me recalculate...
Actually: 2→2 (0), 6→6 (0), 7→8 (1), 8→8 (0), 9→9 (0) gives max = 1.
But with holes [2, 6, 8, 8, 9], optimal assignment gives max distance 2.

Solution

Method 1 - Greedy Sorting Assignment

Intuition

To minimize the maximum distance, we should try to pair each mouse with the closest available hole. Since we want to minimize the maximum distance across all assignments, the optimal strategy is to sort both mice and holes, then pair them in order. This greedy approach ensures that no mouse is unnecessarily far from its assigned hole.

Approach

  1. Sort both the mice array and holes array in ascending order
  2. Pair each mouse with the hole at the same index after sorting
  3. Calculate the distance for each mouse-hole pair
  4. Return the maximum distance among all pairs
  5. This works because sorting ensures optimal pairing that minimizes maximum distance

Code

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

class Solution {
public:
    int assignMice(vector<int>& mice, vector<int>& holes) {
        sort(mice.begin(), mice.end());
        sort(holes.begin(), holes.end());
        
        int maxDist = 0;
        for (int i = 0; i < mice.size(); i++) {
            maxDist = max(maxDist, abs(mice[i] - holes[i]));
        }
        
        return maxDist;
    }
};
 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

import (
    "sort"
)

func assignMice(mice []int, holes []int) int {
    sort.Ints(mice)
    sort.Ints(holes)
    
    maxDist := 0
    for i := 0; i < len(mice); i++ {
        dist := abs(mice[i] - holes[i])
        if dist > maxDist {
            maxDist = dist
        }
    }
    
    return maxDist
}

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

class Solution {
    public int assignMice(int[] mice, int[] holes) {
        Arrays.sort(mice);
        Arrays.sort(holes);
        
        int maxDist = 0;
        for (int i = 0; i < mice.length; i++) {
            maxDist = Math.max(maxDist, Math.abs(mice[i] - holes[i]));
        }
        
        return maxDist;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def assign_mice(self, mice: List[int], holes: List[int]) -> int:
        mice.sort()
        holes.sort()
        
        max_dist = 0
        for i in range(len(mice)):
            max_dist = max(max_dist, abs(mice[i] - holes[i]))
        
        return max_dist

Complexity

  • ⏰ Time complexity: O(N log N), due to sorting both mice and holes arrays
  • 🧺 Space complexity: O(1), only using constant extra space (excluding input modification)

Method 2 - Dynamic Programming with Bitmask

Intuition

We can also solve this using dynamic programming where we try all possible assignments and find the one with minimum maximum distance. This approach uses bitmask to represent which holes are already assigned and explores all valid assignments.

Approach

  1. Use dynamic programming with memoization
  2. State: current mouse index and bitmask representing assigned holes
  3. For each mouse, try assigning it to each unassigned hole
  4. Recursively solve for remaining mice and holes
  5. Return the minimum of maximum distances across all possible assignments
  6. Base case: when all mice are assigned, return 0

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
25
26
27
28
29
30
31
32
33

class Solution {
private:
    unordered_map<string, int> memo;
    
public:
    int assignMiceDP(vector<int>& mice, vector<int>& holes) {
        memo.clear();
        return dp(0, 0, mice, holes);
    }
    
private:
    int dp(int mouseIdx, int mask, vector<int>& mice, vector<int>& holes) {
        if (mouseIdx == mice.size()) {
            return 0;
        }
        
        string key = to_string(mouseIdx) + "," + to_string(mask);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        
        int result = INT_MAX;
        for (int i = 0; i < holes.size(); i++) {
            if (!(mask & (1 << i))) {  // hole i is not assigned
                int dist = abs(mice[mouseIdx] - holes[i]);
                int nextResult = dp(mouseIdx + 1, mask | (1 << i), mice, holes);
                result = min(result, max(dist, nextResult));
            }
        }
        
        return memo[key] = result;
    }
};
 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
32
33
34
35
36
37
38
39
40
41
42
43

import (
    "fmt"
    "strconv"
)

func assignMiceDP(mice []int, holes []int) int {
    memo := make(map[string]int)
    return dpHelper(0, 0, mice, holes, memo)
}

func dpHelper(mouseIdx, mask int, mice, holes []int, memo map[string]int) int {
    if mouseIdx == len(mice) {
        return 0
    }
    
    key := fmt.Sprintf("%d,%d", mouseIdx, mask)
    if val, exists := memo[key]; exists {
        return val
    }
    
    result := int(^uint(0) >> 1) // Max int
    for i := 0; i < len(holes); i++ {
        if (mask & (1 << i)) == 0 { // hole i is not assigned
            dist := abs(mice[mouseIdx] - holes[i])
            nextResult := dpHelper(mouseIdx+1, mask|(1<<i), mice, holes, memo)
            if nextResult > dist {
                result = min(result, nextResult)
            } else {
                result = min(result, dist)
            }
        }
    }
    
    memo[key] = result
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 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

class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    
    public int assignMiceDP(int[] mice, int[] holes) {
        memo.clear();
        return dp(0, 0, mice, holes);
    }
    
    private int dp(int mouseIdx, int mask, int[] mice, int[] holes) {
        if (mouseIdx == mice.length) {
            return 0;
        }
        
        String key = mouseIdx + "," + mask;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < holes.length; i++) {
            if ((mask & (1 << i)) == 0) {  // hole i is not assigned
                int dist = Math.abs(mice[mouseIdx] - holes[i]);
                int nextResult = dp(mouseIdx + 1, mask | (1 << i), mice, holes);
                result = Math.min(result, Math.max(dist, nextResult));
            }
        }
        
        memo.put(key, result);
        return result;
    }
}
 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:
    def assign_mice_dp(self, mice: List[int], holes: List[int]) -> int:
        memo = {}
        
        def dp(mouse_idx: int, mask: int) -> int:
            if mouse_idx == len(mice):
                return 0
            
            key = (mouse_idx, mask)
            if key in memo:
                return memo[key]
            
            result = float('inf')
            for i in range(len(holes)):
                if not (mask & (1 << i)):  # hole i is not assigned
                    dist = abs(mice[mouse_idx] - holes[i])
                    next_result = dp(mouse_idx + 1, mask | (1 << i))
                    result = min(result, max(dist, next_result))
            
            memo[key] = result
            return result
        
        return dp(0, 0)

Complexity

  • ⏰ Time complexity: O(N! × N), where N! represents all possible assignments and N for trying each hole
  • 🧺 Space complexity: O(N × 2^N), for memoization table storing states for each mouse and hole assignment mask

Notes

  • The greedy sorting approach (Method 1) is optimal and much more efficient
  • The DP approach (Method 2) explores all possibilities but has exponential complexity
  • For this problem, the greedy approach works because of the optimal substructure property
  • Sorting both arrays ensures that we don’t have crossing assignments which would increase the maximum distance
  • The problem is essentially about finding the optimal bipartite matching to minimize bottleneck distance