LeetCode 3761 - Minimum Absolute Distance Between Mirror Pairs
We are given an integer array nums. A pair of indices (i, j) is called a mirror pair if: - i < j - reverse(nums[i]) == nums[j] The operation reverse(x) reverses the decimal digits of x and removes any leading zeros that appear after reversal.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math
Solution
Problem Understanding
We are given an integer array nums. A pair of indices (i, j) is called a mirror pair if:
i < jreverse(nums[i]) == nums[j]
The operation reverse(x) reverses the decimal digits of x and removes any leading zeros that appear after reversal. For example:
reverse(12) = 21reverse(120) = 21reverse(1000) = 1
The task is to find the minimum distance j - i among all mirror pairs. Since the problem already guarantees i < j, the absolute distance abs(i - j) is simply j - i.
If no mirror pair exists anywhere in the array, we return -1.
The constraint nums.length <= 10^5 immediately rules out quadratic algorithms. An O(n^2) solution would require up to about 10^10 comparisons, which is far too large. We therefore need a solution that processes each element only a constant number of times, suggesting a hash table based approach.
Several edge cases deserve attention:
- Numbers whose reverse removes trailing zeros, such as
120 → 21. - Multiple occurrences of the same value.
- Numbers that reverse to themselves, such as
33or121. - Arrays containing no mirror pairs.
- Arrays where the minimum distance comes from adjacent indices.
- Arrays where many mirror pairs exist and we must return the smallest distance among them.
Approaches
Brute Force
The most direct approach is to examine every pair (i, j) with i < j.
For each pair, compute reverse(nums[i]) and check whether it equals nums[j]. Whenever a mirror pair is found, update the minimum distance.
This approach is correct because it explicitly checks every possible pair, so no valid mirror pair can be missed. However, there are O(n^2) pairs. With n = 10^5, this becomes infeasible.
Key Insight
Suppose we are currently processing index j with value nums[j].
A mirror pair exists with some earlier index i precisely when
reverse(nums[i]) = nums[j]
Equivalently,
nums[i] = reverse(nums[j])
Therefore, when we arrive at index j, we only need to know whether we have previously seen the value reverse(nums[j]).
Furthermore, if several earlier indices contain the required value, only the most recent one can produce the minimum distance for the current position. If the same value appeared at indices
i1 < i2 < ... < ik < j
then
j - ik < j - ik-1 < ... < j - i1
Thus, for every value, it is sufficient to store its latest occurrence.
A hash map lets us find the latest occurrence of a value in constant expected time.
Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Checks every pair of indices |
| Optimal | O(n · d) | O(n) | Hash map lookup per element, where d is the number of digits, at most 10 |
Since nums[i] ≤ 10^9, digit reversal takes at most 10 iterations, so d is effectively constant and the overall complexity is O(n).
Algorithm Walkthrough
- Create a hash map
last_indexthat stores the most recent index where each value has appeared. - Initialize the answer to infinity.
- Process the array from left to right.
- For the current index
j, computereverse(nums[j]). - Check whether this reversed value exists in
last_index. - If it exists, let
ibe the stored index. Then:
nums[i] = reverse(nums[j])
which implies
reverse(nums[i]) = nums[j]
Therefore (i, j) is a mirror pair. Update the minimum distance with:
j - i
- Store the current index as the latest occurrence of
nums[j]:
last_index[nums[j]] = j
- Continue until all elements have been processed.
- If no mirror pair was ever found, return
-1. Otherwise return the minimum distance recorded.
Why it works
For every index j, a mirror pair ending at j must satisfy:
nums[i] = reverse(nums[j])
for some earlier index i.
The hash map contains the latest occurrence of every value seen so far, so whenever such an i exists, the algorithm finds it. Among all candidate indices with the same value, the latest occurrence yields the smallest distance to j, so no better pair ending at j can be missed.
Taking the minimum over all positions j therefore yields exactly the minimum distance among all mirror pairs.
Python Solution
from typing import List
class Solution:
def minMirrorPairDistance(self, nums: List[int]) -> int:
def reverse_number(x: int) -> int:
reversed_num = 0
while x > 0:
reversed_num = reversed_num * 10 + x % 10
x //= 10
return reversed_num
last_index = {}
answer = float("inf")
for index, value in enumerate(nums):
reversed_value = reverse_number(value)
if reversed_value in last_index:
answer = min(answer, index - last_index[reversed_value])
last_index[value] = index
return -1 if answer == float("inf") else answer
The helper function reverse_number performs digit reversal using arithmetic operations. This automatically removes leading zeros after reversal because integer arithmetic never preserves them.
The hash map last_index stores the most recent occurrence of every value encountered so far.
For each position, the algorithm computes the reversed form of the current value and checks whether that reversed value has already appeared. If it has, a mirror pair exists and the distance is evaluated.
After processing the current position, the hash map is updated so future elements can use this index as their latest occurrence.
Finally, if the answer was never updated, no mirror pair exists and -1 is returned.
Go Solution
func minMirrorPairDistance(nums []int) int {
reverseNumber := func(x int) int {
reversed := 0
for x > 0 {
reversed = reversed*10 + x%10
x /= 10
}
return reversed
}
lastIndex := make(map[int]int)
const INF = int(1e9)
answer := INF
for index, value := range nums {
reversedValue := reverseNumber(value)
if prevIndex, exists := lastIndex[reversedValue]; exists {
distance := index - prevIndex
if distance < answer {
answer = distance
}
}
lastIndex[value] = index
}
if answer == INF {
return -1
}
return answer
}
The Go implementation follows exactly the same logic as the Python version. The hash map is represented by map[int]int. Since Go does not have a built-in infinity value for integers, a sufficiently large sentinel value is used. Integer overflow is not a concern during digit reversal because all inputs are at most 10^9, and the reversed value also fits comfortably within a 32-bit signed integer.
Worked Examples
Example 1
Input:
nums = [12,21,45,33,54]
| Index | Value | Reverse(Value) | Hash Map Before | Pair Found? | Best Answer |
|---|---|---|---|---|---|
| 0 | 12 | 21 | {} | No | ∞ |
| 1 | 21 | 12 | {12:0} | Yes, (0,1) | 1 |
| 2 | 45 | 54 | {12:0,21:1} | No | 1 |
| 3 | 33 | 33 | {12:0,21:1,45:2} | No | 1 |
| 4 | 54 | 45 | {12:0,21:1,45:2,33:3} | Yes, (2,4) | 1 |
Result:
1
Example 2
Input:
nums = [120,21]
| Index | Value | Reverse(Value) | Hash Map Before | Pair Found? |
|---|---|---|---|---|
| 0 | 120 | 21 | {} | No |
| 1 | 21 | 12 | {120:0} | No |
At first glance no pair is detected when processing 21, because the algorithm checks for previous 12.
However, when processing 120, we should observe that:
reverse(120) = 21
and later 21 appears.
The mirror pair is:
(0,1)
Distance:
1
Result:
1
The hash-map formulation captures this because when index 1 is processed, we need to detect a prior value whose reverse equals 21. Equivalently, we must store reversals seen so far. An implementation based on storing original values would miss this case. The correct implementation stores information so that reverse(nums[i]) can be matched against future values.
Let us refine the invariant accordingly: store the latest index associated with each reversed value.
Correct State Trace for Example 2
| Index | Value | Reverse(Value) | Stored Reversal Map Before | Pair Found? |
|---|---|---|---|---|
| 0 | 120 | 21 | {} | No |
| 1 | 21 | 12 | {21:0} | Yes, (0,1) |
Distance:
1
Example 3
Input:
nums = [21,120]
| Index | Value | Reverse(Value) | Stored Reversal Map Before | Pair Found? |
|---|---|---|---|---|
| 0 | 21 | 12 | {} | No |
| 1 | 120 | 21 | {12:0} | No |
No mirror pair exists.
Result:
-1
Corrected Optimal Implementation
The worked examples reveal the exact invariant needed. We should store the latest index of reverse(nums[i]), not merely nums[i].
Python
from typing import List
class Solution:
def minMirrorPairDistance(self, nums: List[int]) -> int:
def reverse_number(x: int) -> int:
result = 0
while x:
result = result * 10 + x % 10
x //= 10
return result
latest = {}
answer = float("inf")
for index, value in enumerate(nums):
if value in latest:
answer = min(answer, index - latest[value])
latest[reverse_number(value)] = index
return -1 if answer == float("inf") else answer
Go
func minMirrorPairDistance(nums []int) int {
reverseNumber := func(x int) int {
result := 0
for x > 0 {
result = result*10 + x%10
x /= 10
}
return result
}
latest := make(map[int]int)
const INF = int(1e9)
answer := INF
for index, value := range nums {
if prev, exists := latest[value]; exists {
distance := index - prev
if distance < answer {
answer = distance
}
}
latest[reverseNumber(value)] = index
}
if answer == INF {
return -1
}
return answer
}
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element is processed once, digit reversal is at most 10 operations |
| Space | O(n) | Hash map may store one entry per distinct value |
Because every number contains at most ten decimal digits, reversing a number is constant time. Therefore the total running time is linear in the length of the array. The hash map can contain up to one entry for each distinct reversed value, giving linear auxiliary space.
Test Cases
s = Solution()
assert s.minMirrorPairDistance([12, 21, 45, 33, 54]) == 1 # provided example
assert s.minMirrorPairDistance([120, 21]) == 1 # trailing zeros
assert s.minMirrorPairDistance([21, 120]) == -1 # no pair
assert s.minMirrorPairDistance([11]) == -1 # single element
assert s.minMirrorPairDistance([33, 33]) == 1 # self-reversing value
assert s.minMirrorPairDistance([12, 99, 21]) == 2 # one pair distance 2
assert s.minMirrorPairDistance([12, 21, 21]) == 1 # repeated values
assert s.minMirrorPairDistance([1200, 21, 120]) == 1 # multiple reversals
assert s.minMirrorPairDistance([10, 1]) == 1 # reverse removes zero
assert s.minMirrorPairDistance([1000, 1, 1000, 1]) == 1 # repeated mirror pairs
assert s.minMirrorPairDistance([13, 31, 13, 31]) == 1 # many mirror pairs
assert s.minMirrorPairDistance([123456789, 987654321]) == 1 # large values
Test Summary
| Test | Why |
|---|---|
[12,21,45,33,54] |
Basic example with multiple mirror pairs |
[120,21] |
Leading zeros disappear after reversal |
[21,120] |
Reverse relationship is directional |
[11] |
Minimum size input |
[33,33] |
Self-reversing numbers |
[12,99,21] |
Non-adjacent mirror pair |
[12,21,21] |
Duplicate values |
[1200,21,120] |
Multiple candidates involving trailing zeros |
[10,1] |
Reverse becomes a single digit |
[1000,1,1000,1] |
Repeated mirror relationships |
[13,31,13,31] |
Several overlapping mirror pairs |
[123456789,987654321] |
Large numbers near constraint limit |
Edge Cases
Numbers With Trailing Zeros
Values such as 120, 1200, and 10 are easy to mishandle if reversal is implemented using string manipulation without removing leading zeros afterward. Arithmetic reversal naturally produces 21, 21, and 1, respectively. The implementation uses digit extraction and reconstruction, so these cases are handled correctly.
Self-Reversing Numbers
Numbers such as 33, 121, and 7 satisfy:
reverse(x) = x
Two occurrences of such a value form a valid mirror pair. The algorithm correctly records the latest index associated with the reversed value, which is the same number, allowing later occurrences to be matched immediately.
Multiple Occurrences of the Same Mirror Value
Suppose:
[12, 12, 12, 21]
The valid mirror pairs are (0,3), (1,3), and (2,3). The minimum distance is obtained using the latest previous occurrence. By storing only the most recent index for each reversed value, the algorithm automatically computes the smallest possible distance for every ending position.
No Mirror Pair Exists
Arrays such as:
[21, 120]
contain no valid pair. The answer variable remains unchanged from its sentinel value, and the implementation returns -1, exactly as required.