3761. Minimum Absolute Distance Between Mirror Pairs

MediumArrayHash TableMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

A mirror pair is a pair of indices (i, j) that satisfies the following conditions:

0 <= i < j < nums.length, and
reverse(nums[i]) == nums[j], where reverse(x) denotes the integer formed by reversing the digits of x. Leading zeros are omitted after reversing. For example, reverse(120) = 21.

Your task is to return the minimum absolute distance between the indices of any mirror pair. The absolute distance between indices i and j is abs(i - j).

If no mirror pair exists, return -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Using a hash table to map reversed values to their latest indices enables O(n) matching of mirror pairs in a single pass.

Open in Flowchart

Intuition

The key observation is that for a mirror pair (i, j) with i < j, the condition is reverse(nums[i]) == nums[j]. This means that when we are looking at index j, we want to find some earlier index i whose reversed value matches nums[j].

A brute-force approach would check every pair (i, j), but that takes O(n^2) time. Instead, we can process the array in a single pass and remember useful information along the way.

The trick is to think about it from the perspective of the later index j. As we scan from left to right and reach index j with value x = nums[j], we want to know: has there been any earlier index i such that reverse(nums[i]) == x? If we have been storing, for each value reverse(nums[i]), the most recent index i where it appeared, then we can directly look up whether x exists among those stored values.

This is why we use a hash table that maps reverse(nums[i]) to its latest index i. When we arrive at index i with value x:

First, we check if x is already a key in the hash table. If it is, that key was placed by some earlier index j' where reverse(nums[j']) == x, forming a valid mirror pair, and we update the answer with the current distance.
Then, we store reverse(x) mapped to the current index i, so that future indices can match against it.

Because we always store the latest index for each reversed value, and we process indices in increasing order, the distance i - pos[x] is automatically the smallest possible for that matching pair at this moment. Tracking the minimum across all such matches gives us the final answer. This reduces the time complexity to O(n).

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Hash Table

We use a hash table pos to record the last occurrence position of each reversed number.

We first initialize the answer ans = inf.

Next, we iterate through the array nums. For each index i and its corresponding number x = nums[i]:

If the key x exists in pos, it means there exists an earlier index j such that reverse(nums[j]) equals x, forming a valid mirror pair. In this case, we update the answer to ans = min(ans, i - pos[x]).
Then, we update pos[reverse(x)] = i, recording the current index against the reversed value of x so that future indices can match against it.

The helper function reverse(x) builds the reversed integer digit by digit:

def reverse(x: int) -> int:
    y = 0
    while x:
        v = x % 10
        y = y * 10 + v
        x //= 10
    return y

It repeatedly takes the last digit v = x % 10, appends it to y via y = y * 10 + v, and removes the last digit from x with x //= 10. Leading zeros naturally disappear because they do not contribute to y.

Finally, if the answer ans is still equal to inf, it means no mirror pair exists, so we return -1; otherwise, we return ans.

The time complexity is O(n * log M), and the space complexity is O(n). Here, n is the length of the array nums, and M is the maximum value in the array (the log M factor comes from reversing the digits of each number).

Example Walkthrough

Let's trace through the Hash Table approach with a small example:

Input: nums = [21, 5, 12, 50]

We want to find the minimum absolute distance between any mirror pair (i, j) where reverse(nums[i]) == nums[j].

We initialize:

pos = {} (empty hash table mapping reverse(value) → latest index)
ans = inf

Now we scan from left to right:

Index i = 0, x = 21

Is x = 21 a key in pos? pos is empty, so no match.
Compute reverse(21) = 12. Store pos[12] = 0.
State: pos = {12: 0}, ans = inf

Index i = 1, x = 5

Is x = 5 a key in pos? pos = {12: 0}, so no match.
Compute reverse(5) = 5. Store pos[5] = 1.
State: pos = {12: 0, 5: 1}, ans = inf

Index i = 2, x = 12

Is x = 12 a key in pos? Yes! pos[12] = 0. This means index 0 had value 21, and reverse(21) = 12 == nums[2]. A valid mirror pair (0, 2) exists.
Update ans = min(inf, 2 - 0) = 2.
Compute reverse(12) = 21. Store pos[21] = 2.
State: pos = {12: 0, 5: 1, 21: 2}, ans = 2

Index i = 3, x = 50

Is x = 50 a key in pos? pos = {12: 0, 5: 1, 21: 2}, so no match.
Compute reverse(50) = 5 (the trailing zero vanishes). Store pos[5] = 3, overwriting the older index 1 so future matches use the nearest earlier index.
State: pos = {12: 0, 5: 3, 21: 2}, ans = 2

Result: ans = 2, returned as the answer.

The mirror pair (0, 2) is found because reverse(nums[0]) = reverse(21) = 12 = nums[2], giving an absolute distance of |0 - 2| = 2. Notice how storing reverse(x) keyed by the latest index ensures that whenever a later value matches, we measure against the closest previous candidate, yielding the minimum distance in a single O(n) pass.

Solution Implementation

1from typing import List
2from math import inf
3
4
5class Solution:
6    def minMirrorPairDistance(self, nums: List[int]) -> int:
7        # Reverse the digits of a non-negative integer.
8        # Example: 123 -> 321
9        def reverse(x: int) -> int:
10            reversed_value = 0
11            while x:
12                digit = x % 10                          # extract the last digit
13                reversed_value = reversed_value * 10 + digit  # append it to the result
14                x //= 10                                # drop the last digit
15            return reversed_value
16
17        # last_index records, for each value we have already "registered",
18        # the most recent index at which it can be matched.
19        # The trick: when processing nums[i], we store the *reversed* form of
20        # nums[i] at index i. So a later element nums[j] equal to that reversed
21        # form forms a "mirror pair" (nums[i] reversed == nums[j]).
22        last_index = {}
23        ans = inf
24
25        for i, x in enumerate(nums):
26            # If the current value matches a previously stored reversed value,
27            # we found a mirror pair; update the minimum distance.
28            if x in last_index:
29                ans = min(ans, i - last_index[x])
30
31            # Register the reversed form of the current value at this index,
32            # so future elements equal to it can be paired with index i.
33            last_index[reverse(x)] = i
34
35        # If no mirror pair was found, return -1; otherwise the smallest distance.
36        return -1 if ans == inf else ans
37

1class Solution {
2    /**
3     * Finds the minimum distance between a "mirror pair".
4     * A mirror pair (i, j) with i < j satisfies: nums[i] equals the
5     * digit-reversal of nums[j] (i.e. nums[i] == reverse(nums[j])).
6     * The distance is defined as j - i.
7     *
8     * @param nums the input array of numbers
9     * @return the minimum mirror pair distance, or -1 if none exists
10     */
11    public int minMirrorPairDistance(int[] nums) {
12        int n = nums.length;
13
14        // Maps the reversed value of a previously seen number to the
15        // most recent index where that reversed value was produced.
16        // Key:   reverse(nums[k]) for some earlier index k
17        // Value: the index k
18        Map<Integer, Integer> reversedValueToIndex = new HashMap<>(n);
19
20        // Initialize the answer to a value larger than any valid distance,
21        // so we can detect the "no pair found" case at the end.
22        int minDistance = n + 1;
23
24        for (int i = 0; i < n; ++i) {
25            // If some earlier element's reversal equals the current value,
26            // then (earlierIndex, i) forms a valid mirror pair.
27            if (reversedValueToIndex.containsKey(nums[i])) {
28                int earlierIndex = reversedValueToIndex.get(nums[i]);
29                minDistance = Math.min(minDistance, i - earlierIndex);
30            }
31
32            // Record the reversal of the current value, mapped to its index,
33            // so future elements can match against it.
34            reversedValueToIndex.put(reverse(nums[i]), i);
35        }
36
37        // If minDistance was never updated, no mirror pair exists.
38        return minDistance > n ? -1 : minDistance;
39    }
40
41    /**
42     * Reverses the decimal digits of a non-negative integer.
43     * For example: 123 -> 321, 120 -> 21.
44     *
45     * @param x the non-negative integer to reverse
46     * @return the integer formed by reversing the digits of x
47     */
48    private int reverse(int x) {
49        int reversed = 0;
50        // Strip digits from the least significant end of x and
51        // append them to the result, effectively reversing the number.
52        for (; x > 0; x /= 10) {
53            reversed = reversed * 10 + x % 10;
54        }
55        return reversed;
56    }
57}
58

1class Solution {
2public:
3    int minMirrorPairDistance(vector<int>& nums) {
4        int n = nums.size();
5        // Initialize answer to a value larger than any valid distance.
6        int ans = n + 1;
7        // Map from a value to the most recent index where it can be matched.
8        unordered_map<int, int> lastPos;
9
10        // Helper lambda that reverses the digits of a non-negative integer.
11        // For example, reverseDigits(123) -> 321.
12        auto reverseDigits = [](int x) {
13            int reversed = 0;
14            for (; x > 0; x /= 10) {
15                reversed = reversed * 10 + x % 10;
16            }
17            return reversed;
18        };
19
20        for (int i = 0; i < n; ++i) {
21            // If the current value was registered earlier as the reverse of
22            // some previous element, we found a mirror pair. Update the answer
23            // with the smallest index distance.
24            auto it = lastPos.find(nums[i]);
25            if (it != lastPos.end()) {
26                ans = min(ans, i - it->second);
27            }
28            // Register the reverse of the current value so that a future element
29            // equal to this reverse can be matched with the current index.
30            lastPos[reverseDigits(nums[i])] = i;
31        }
32
33        // If no mirror pair was found, ans stays greater than n; return -1.
34        return ans > n ? -1 : ans;
35    }
36};
37

1/**
2 * Finds the minimum distance between a "mirror pair" of indices.
3 * A mirror pair (j, i) satisfies: reverse(nums[j]) === nums[i], where j < i.
4 * The distance is defined as (i - j).
5 *
6 * @param nums - The input array of non-negative integers.
7 * @returns The minimum mirror pair distance, or -1 if no such pair exists.
8 */
9function minMirrorPairDistance(nums: number[]): number {
10    const length: number = nums.length;
11
12    // Maps a reversed value to the most recent index whose reverse equals that value.
13    // Key: reversed digit value, Value: index in nums.
14    const lastIndexByReverse: Map<number, number> = new Map<number, number>();
15
16    // Initialize the answer to a value larger than any valid distance.
17    let minDistance: number = length + 1;
18
19    /**
20     * Reverses the digits of a non-negative integer.
21     * For example, reverseDigits(123) returns 321.
22     *
23     * @param value - The non-negative integer to reverse.
24     * @returns The integer formed by reversing the digits of value.
25     */
26    const reverseDigits = (value: number): number => {
27        let reversed: number = 0;
28        for (; value > 0; value = Math.floor(value / 10)) {
29            // Append the last digit of value to reversed.
30            reversed = reversed * 10 + (value % 10);
31        }
32        return reversed;
33    };
34
35    for (let i = 0; i < length; ++i) {
36        // If a previous element's reverse matches the current value,
37        // we have found a mirror pair ending at index i.
38        if (lastIndexByReverse.has(nums[i])) {
39            const previousIndex: number = lastIndexByReverse.get(nums[i])!;
40            minDistance = Math.min(minDistance, i - previousIndex);
41        }
42
43        // Record the reverse of the current value mapped to the current index,
44        // so future elements can detect a mirror pair with this one.
45        lastIndexByReverse.set(reverseDigits(nums[i]), i);
46    }
47
48    // If minDistance was never updated below the sentinel, no mirror pair exists.
49    return minDistance > length ? -1 : minDistance;
50}
51

Time and Space Complexity

Time complexity: O(n × log M), where n is the length of the array nums, and M is the maximum value in the array. The algorithm iterates through the array once, performing a single pass of n elements. For each element, the reverse function processes the digits of the number, taking O(log M) time since the number of digits is proportional to log M. Therefore, the overall time complexity is O(n × log M).
Space complexity: O(n). This is used to store the hash table pos, which can hold up to n key-value pairs in the worst case.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Storing reverse(x) only after checking, but overwriting an earlier (closer) match incorrectly

A subtle issue is reasoning about which index gives the minimum distance. Since we always store the most recent index for each reversed value (last_index[reverse(x)] = i), and we scan left to right, the match i - last_index[x] always uses the closest preceding candidate. This is correct, but a common mistake is to use a structure that keeps the first occurrence instead of the latest one. If you accidentally store only the earliest index (e.g., with last_index.setdefault(reverse(x), i)), you may compute a larger-than-necessary distance and miss the true minimum.

Wrong:

last_index.setdefault(reverse(x), i)   # keeps earliest index -> may overestimate distance

Correct:

last_index[reverse(x)] = i             # always keep the latest index -> guarantees minimum

Pitfall 2: Confusing the direction of the mirror condition

The condition is reverse(nums[i]) == nums[j] with i < j. It is tempting to instead store x itself and look up reverse(x):

# Buggy alternative
if reverse(x) in last_index:
    ans = min(ans, i - last_index[reverse(x)])
last_index[x] = i

This actually checks nums[i] == reverse(nums[j]) for the earlier index j, i.e. reverse(nums[j]) == nums[i]. This is the same relation mathematically (reverse is symmetric: reverse(a) == b ⟺ a == reverse(b) only when no trailing-zero information is lost). The trap is the trailing-zero asymmetry: reverse(120) = 21, but reverse(21) = 12 ≠ 120. Because of this, the two formulations are not equivalent. The given solution stores reverse(x) and matches against the raw later value x, which correctly models reverse(nums[i]) == nums[j]. Swapping the direction silently changes the semantics for numbers with trailing zeros.

Pitfall 3: Mishandling trailing zeros and the value 0

Reversing numbers with trailing zeros drops them (reverse(120) = 21), which is intended. However:

reverse(0) returns 0 because the while x: loop never executes when x == 0. This is correct, but if you ever rewrite the loop as a do-while-style construct, make sure 0 still maps to 0.
Negative numbers are not handled. The loop while x: with x % 10 and x //= 10 behaves unexpectedly for negatives in Python (floor division rounds toward negative infinity). If the constraints allow negative values, you must strip and reattach the sign:

def reverse(x: int) -> int:
    sign = -1 if x < 0 else 1
    x = abs(x)
    reversed_value = 0
    while x:
        reversed_value = reversed_value * 10 + x % 10
        x //= 10
    return sign * reversed_value

Pitfall 4: Returning inf instead of -1

Forgetting the final guard return -1 if ans == inf else ans will leak the sentinel inf (a float) as the result when no mirror pair exists. Always convert the "not found" sentinel back to the required -1.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering