Assign Mice to Holes | InterviewBit | Solution Explained
I explain the solution to Assign Mice to Holes on InterviewBit using visuals in simple words.
0. Assign Mice to Holes: Problem Discussion
0.0. IO Format
- input:
- N mice and N holes’ positions are given. Each mice takes 1 unit of time to move 1 unit left or right
- output:
- the minimum time taken to assure all mice are in holes
0.1. Examples
Take the case where we have [3,2,-4] as the positions of the mice and [0,-2,4] as the positions of the holes.
The mice at position -4 moves to the hole at -2. Similarly, mice at 2 moves to hole at 0 and mice at 3 moves to hole at 4.
This gives the total time as max(|-4 – -2|, |2 – 0|, |3 – 4|) = 2.
1. Assign Mice to Holes: Observations & Logic
1.0. Intuitions
The first thing that happened by default, as we plotted these mice and holes is that they got sorted according to their positions.
We then realize that we simply assigned the mice at index 0 to hole at its index 0 (both after sorting). In general, can we say that mice at index i gets assigned the hole at index i?
If we say that, the assumption then becomes that two mice will never cross, and only go to their corresponding holes.
Can we prove it?
1.1. Proof
Assume that the mice do indeed cross. Let’s take a simpler case.
Since the mice do not have individual identities, we can split the path at the crossing point, and say that the left mice goes to the left hole, but now ends up taking a longer path, to do the same thing as before – it would simply be better if the mice did not cross. Thus, we have proved by contradiction that the mice will never cross each other.
2. Assign Mice to Holes: Optimized Implementation
2.0. Code
class Solution: # @param A : list of integers # @param B : list of integers # @return an integer def mice(self, A, B): A.sort() B.sort() ans = 0 for a, b in zip(A, B): ans = max(ans, abs(a - b)) return ans
2.1. Complexity Analysis
- Time:
O(NlogN)
, for sorting both the arrays A and B. - Space:
O(N)
, the space complexity for sorting in Python3. Other languages might have different space complexities depending upon the algorithm they use.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Seats | InterviewBit | Solution Explained
June 13, 2022
If we use the method suggested with 2,2,3,3,0,0 we will also get 010 as an answer, yet it’s not the majority element