Minimum Absolute Distance Between Mirror Pairs

Problem summary

We are given an array nums.

A valid mirror pair is a pair of indices (i, j) where:

• i < j
• reverse(nums[i]) == nums[j]

We need the smallest distance j - i among all such pairs. If no pair exists, return -1.

Key observation

The pair direction matters.

For a pair (i, j), only the number at the left index is reversed:

reverse(nums[i]) == nums[j]

That is why:

• [120, 21] has a mirror pair, because reverse(120) = 21
• [21, 120] does not, because reverse(21) = 12, not 120

So while scanning from left to right, we only need to know whether the current value can complete a pair started by an earlier index.

Intuition

Suppose we already saw some index j.

If reverse(nums[j]) = 54, then that old index is waiting for a future value 54.

So instead of storing nums[j], store the value it wants to match:

previous[reverse(nums[j])] = j

Now when we stand at index i with value x = nums[i], we can ask:

Has any previous index been waiting for x?

If yes, that previous index and i form a mirror pair.

Why store only the most recent index?

For a fixed right endpoint i, the best left endpoint is the closest valid one.

If two earlier indices are both waiting for value x, say:

j1 < j2 < i

then:

i - j2 < i - j1

So the most recent index is always at least as good as any older one for future matches. That means one index per waiting value is enough.

One-pass approach

Maintain a hash map previous.

previous[value] means:

the most recent index whose reversed number equals value

For each index i:

1. Let value = nums[i].
2. If value exists in previous, update the answer with i - previous[value].
3. Compute reverse(value).
4. Store previous[reverse(value)] = i.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minMirrorPairDistance(int[] nums) {
        Map<Integer, Integer> previous = new HashMap<>();
        int answer = nums.length + 1;

        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];

            if (previous.containsKey(value)) {
                answer = Math.min(answer, i - previous.get(value));
            }

            previous.put(reverse(value), i);
        }

        return answer == nums.length + 1 ? -1 : answer;
    }

    private int reverse(int value) {
        int reversed = 0;

        while (value > 0) {
            reversed = reversed * 10 + value % 10;
            value /= 10;
        }

        return reversed;
    }
}

Dry run

Take:

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

Start with an empty map.

At index 0, value 12:

• no earlier number is waiting for 12
• store previous[21] = 0

At index 1, value 21:

• previous[21] = 0, so (0, 1) is a mirror pair
• distance is 1
• store previous[12] = 1

At index 2, value 45:

• no earlier number is waiting for 45
• store previous[54] = 2

At index 3, value 33:

• no earlier number is waiting for 33
• store previous[33] = 3

At index 4, value 54:

• previous[54] = 2, so (2, 4) is a mirror pair
• distance is 2
• store previous[45] = 4

The minimum distance is 1.

Reversing a number

To reverse digits without converting to a string:

reversed = reversed * 10 + value % 10
value = value / 10

This naturally removes leading zeros after reversal.

For example:

120 -> 21

because the first reversed digit is 0, and integer arithmetic does not keep leading zeros.

Correctness argument

When the scan reaches index i, the map contains exactly the latest index j < i for each value x such that reverse(nums[j]) = x.

If nums[i] exists in the map, then there is an earlier index j where:

reverse(nums[j]) = nums[i]

So (j, i) is a valid mirror pair, and i - j is a candidate answer.

If multiple earlier indices can match nums[i], keeping the latest one gives the smallest distance for this right endpoint. Older matching indices are farther away and can never improve the answer for the same i.

Because every index is processed once as a possible right endpoint, every valid mirror pair is considered when its right endpoint is reached. Therefore, the minimum candidate distance found by the algorithm is the correct answer.

Complexity analysis

Let n be the length of nums, and let C be the maximum value in nums.

Time Complexity: O(n log C)

• the array is scanned once
• each hash map operation is O(1) on average
• reversing a number takes O(log C) digits

Space Complexity: O(n)

• in the worst case, the hash map can store one waiting value for every index

Common mistakes

1. Treating mirror pairs as symmetric

The condition is reverse(nums[i]) == nums[j] with i < j. You should not also assume reverse(nums[j]) == nums[i].

2. Storing the original value instead of the reversed value

The current number must be checked against what previous numbers are waiting for. That is why the key is reverse(previous number).

3. Keeping the earliest index

For minimum distance, keep the latest index for each waiting value. The latest matching left endpoint is always closest to a future right endpoint.