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.

Assign Mice to Holes: example test case

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.

Assign Mice to Holes: example test case solution

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.

Assign Mice to Holes: proof by contradiction

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.

Assign Mice to Holes: proof conclusion

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.

Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

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

    Leave a Reply to Makarand Cancel reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.