414. Minimum Absolute Distance Between Mirror Pairs

Try every ordered pair (i, j) with i < j, reverse nums[i] and check whether it equals nums[j]. Track the smallest j - i.

Approach

1. Define rev(x) = integer formed by reversing the decimal digits of x (leading zeros dropped).
2. For each i from 0 to n - 2:
   • For each j from i + 1 to n - 1:
     • If rev(nums[i]) == nums[j], record j - i as a candidate.
3. Return the minimum, or -1 if none found.

Complexity

• Time: O(n² · L) where L is the number of digits. With n = 10^5 this TLEs.
• Space: O(L) for the reversal.

import java.util.*;

class Solution {
    public int minMirrorPairDistance(int[] nums) {
        int n = nums.length;
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int rev = reverse(nums[i]);
            for (int j = i + 1; j < n; j++) {
                if (nums[j] == rev) {
                    best = Math.min(best, j - i);
                    break;
                }
            }
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private int reverse(int x) {
        int rev = 0;
        while (x > 0) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }
}

Walk left to right and remember, for each value v you've seen so far, the most recent index i where rev(nums[i]) == v. Then when you arrive at a position j whose value matches one of those vs, you've just closed a mirror pair — and because we stored the most recent such i, the distance j - i is the smallest possible for that j.

Why naive matching is tricky

A mirror pair requires rev(nums[i]) == nums[j] with i < j. Notice this relation is not symmetric: rev loses leading zeros, so rev(120) = 21 but rev(21) = 12, not 120. That asymmetry means we have to think carefully about which side of the pair we're standing on while scanning.

We pick a side: as we walk through the array with index i, treat nums[i] as the right side of a potential pair. We're looking for some earlier index i' < i whose value's reverse equals nums[i] — that is, rev(nums[i']) == nums[i]. So we should keep a map keyed by rev(nums[i']), valued at the index i'.

Steps

1. Initialise last_rev = {} (maps rev(value) → most recent index where that value appeared) and best = +∞.
2. For each i from 0 to n - 1:
   • Look up: if nums[i] is a key in last_rev, then (last_rev[nums[i]], i) is a valid mirror pair. Update best = min(best, i - last_rev[nums[i]]).
   • Record: set last_rev[rev(nums[i])] = i. Future indices j > i can match nums[i] against their own value via this entry.
3. Return best if it's finite, else -1.

Walk-through 1: nums = [12, 21, 45, 33, 54]

rev of each: rev(12)=21, rev(21)=12, rev(45)=54, rev(33)=33, rev(54)=45.

Answer: 1. ✓

Walk-through 2: nums = [21, 120]

Answer: -1. ✓

This is the case that catches the asymmetry: rev(21) = 12 and rev(120) = 21, but neither value appears as the right side of a mirror pair, so there's no match.

Why we key the map by rev(value), not by value

If we keyed by value and looked up rev(nums[i]), we'd be asking "did some earlier value equal rev(nums[i])?" — i.e. nums[earlier] == rev(nums[i]). That requires reversal symmetry to be a mirror pair, which fails for values with trailing zeros (120 vs 21). Keying by rev(value) matches the true mirror-pair condition directly.

Edge cases

• Palindromic values (e.g. 33): rev(33) = 33. So one occurrence of 33 records last_rev[33] = i, and a later occurrence finds itself on the lookup. Distance equals the gap between consecutive 33s.
• n == 1: loop runs once, best stays ∞, return -1.
• Trailing zeros: rev(100) = 1. So 100 records last_rev[1] = i, and a later 1 would match it. Conversely, looking for a later 100 would not match a previous 1, because rev(1) = 1, not 100. The asymmetry is handled correctly by this keying.

Complexity

• Time: O(n · L) where L is the digit count (≤ 10).
• Space: O(n) for the map.