Problem Statement in English
You’re given an array of integers nums.
A pair of indices (i, j) is called a mirror pair if nums[i] is equal to the reverse of nums[j] and i < j. The absolute distance of a mirror pair is defined as |i - j|.
Your task is to find the minimum absolute distance among all mirror pairs in the array. If there are no mirror pairs, return -1.
Approach
We can use a hashmap to store the indices of each number in the array. For each number, we can find its reverse and check if it exists in the hashmap.
If it does, we can use binary search to find the closest index of the reverse number that is greater than the current index.
We can then calculate the absolute distance and keep track of the minimum distance found.
And we’re done!
Solution in Python
class Solution:
def minMirrorPairDistance(self, nums: List[int]) -> int:
hm = defaultdict(list)
N = len(nums)
if N == 1:
return -1
def nrev(x):
return int(str(x)[::-1])
for i, v in enumerate(nums):
hm[v].append(i)
res = []
for i in range(len(nums)):
v = nums[i]
rv = nrev(v)
arr = hm[rv]
if not arr:
res.append(inf)
continue
pos = bisect_left(arr, i)
temp = inf
if 0 <= pos - 1 and i < arr[pos - 1] and not (v == rv and arr[pos - 1] == i):
temp = min(temp, abs(arr[pos - 1] - i))
if 0 <= pos < len(arr) and i < arr[pos] and not (v == rv and arr[pos] == i):
temp = min(temp, abs(arr[pos] - i))
if pos + 1 < len(arr) and i < arr[pos + 1] and not (v == rv and arr[pos + 1] == i):
temp = min(temp, abs(arr[pos + 1] - i))
res.append(temp if temp != inf else inf)
final = min(res)
return -1 if final == inf else final
Complexity
Time: $O(n \log n)$
Since we iterate through the array and for each element, we perform a binary search on the list of indices.Space: $O(n)$
Since we store the indices of each number in a hashmap.
And we are done.