leetcode solution

LeetCode 3761 Explained: Mirror Pairs Solution with Python

by

In this problem, a mirror pair is a pair of indices (i, j) such that i < j and reverse(nums[i]) == nums[j]. Reversing drops leading zeros, so reverse(120) = 21. The goal is to return the minimum index distance among all such pairs, or -1 if none exist. The constraints are large enough—up to 10^5 elements—that a brute-force O(n^2) scan will time out.

Key observation

Suppose we are scanning the array from left to right and we are currently at index i with value x = nums[i].

We want to know whether there exists some earlier index j such that:

  • reverse(nums[j]) == x

That means when we visited index j, if we had stored reverse(nums[j]), then at index i we could immediately check whether x matches one of those stored values.

So the idea is:

  • Maintain a hash map pos
  • pos[val] = latest index j such that reverse(nums[j]) == val

Then for each current x = nums[i]:

  1. If x is already in pos, then we found a mirror pair ending at i
  2. Its distance is i - pos[x]
  3. Then store reverse(x) at index i for future matches

This turns the problem into a single pass with hashing. The official constraints and examples support this approach well.

Why storing the latest index is enough

For a fixed value x, suppose multiple earlier indices could pair with the current index i. To minimize i - j, we want the largest possible valid j, not the earliest one.

That is why the hash map should store the most recent index for each reversed value.

Example:

  • nums = [12, 99, 21]
  • At index 0, reverse(12) = 21, so store pos[21] = 0
  • At index 2, value is 21, so distance is 2 - 0 = 2

If there had been another more recent index producing the same reversed value, that one would give a smaller distance, so overwriting is correct.

Dry run

Take:

nums = [12, 21, 45, 33, 54]

Mirror pairs here include (0,1) because reverse(12) = 21, and (2,4) because reverse(45) = 54. The minimum answer is 1.

Now scan left to right:

  • i = 0, x = 12
    • 12 not in map
    • store reverse(12) = 21 → pos[21] = 0
  • i = 1, x = 21
    • 21 is in map at index 0
    • candidate answer = 1 - 0 = 1
    • store reverse(21) = 12 → pos[12] = 1
  • i = 2, x = 45
    • not in map
    • store 54 → pos[54] = 2
  • i = 3, x = 33
    • not in map
    • store 33 → pos[33] = 3
  • i = 4, x = 54
    • 54 is in map at index 2
    • candidate answer = 4 - 2 = 2
    • minimum remains 1

Final answer: 1.

Algorithm

  1. Create a hash map pos
  2. Initialize ans = infinity
  3. For each index i and value x:
    • If x exists in pos, update ans = min(ans, i - pos[x])
    • Compute reverse(x)
    • Set pos[reverse(x)] = i
  4. If ans was never updated, return -1; otherwise return ans

Python solution

from typing import List

class Solution:
    def minMirrorPairDistance(self, nums: List[int]) -> int:
        def reverse_num(x: int) -> int:
            rev = 0
            while x > 0:
                rev = rev * 10 + x % 10
                x //= 10
            return rev

        pos = {}
        ans = float('inf')

        for i, x in enumerate(nums):
            if x in pos:
                ans = min(ans, i - pos[x])

            pos[reverse_num(x)] = i

        return -1 if ans == float('inf') else ans

Complexity

Each element is processed once, and reversing a number takes time proportional to its digit count. Since nums[i] <= 10^9, that is at most 10 digits, so the solution runs in O(n * log M) where M is the maximum value, with O(n) extra space for the hash map.

Common mistakes

1. Using brute force

Checking every pair (i, j) gives O(n^2), which is too slow for n = 10^5.

2. Storing the earliest index instead of the latest

To minimize distance, you want the closest previous match, so keep the most recent index.

3. Mishandling leading zeros

reverse(120) should become 21, not 021. Integer reversal naturally handles this. The problem explicitly defines reversal this way.

Takeaway

This is a neat hash-map pattern:

  • convert the condition into a lookup target
  • scan once
  • store exactly what future elements will need

Instead of asking, “for this index, who can I pair with?”, precompute the answer shape so future indices can match in O(1) average time.

Leave a Comment