nks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[6586,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1d:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:T496,

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

 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**.

1c:T60b,

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

[{"language":"Java","code":"import java.util.*;\nclass Solution {\n\t// A - mice; B - holes\n\tpublic int mice(ArrayList<Integer> A, ArrayList<Integer> B) {\n\t\tif (A.size() != B.size()) {\n\t\t\treturn -1;\n\t\t}\n\t\tCollections.sort(A);\n\t\tCollections.sort(B);\n\t\tint max = 0;\n\t\tfor (int i = 0; i < A.size(); i++) {\n\t\t\tmax = Math.max(max, Math.abs(A.get(i) - B.get(i)));\n\t\t}\n\t\treturn max;\n\t}\n}","lang":"java"},{"language":"Python","code":"class Solution:\n\tdef mice(self, mice, holes):\n\t\tif len(mice) != len(holes):\n\t\t\treturn -1\n\t\tmice.sort()\n\t\tholes.sort()\n\t\tmax_time = 0\n\t\tfor m, h in zip(mice, holes):\n\t\t\tmax_time = max(max_time, abs(m - h))\n\t\treturn max_time","lang":"python"}]

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.

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wrap items-start justify-between gap-4","children":[["$","h1",null,{"className":"text-4xl

Related Tags

Continue Practicing