3761. Minimum Absolute Distance Between Mirror Pairs

Array
Hash Table

TIME

O(n)

SPACE

O(n)

Intuition

For a mirror pair (i, j) with i < j, we need reverse(nums[i]) == nums[j]. Process right to left, tracking the smallest index for each value seen so far.

Solution

Reverse Function

def reverse(x):
    return int(str(x)[::-1])

Note: reverse(120) = 21 (leading zeros dropped).

One-Pass Algorithm (Right to Left)

Maintain map: value -> smallest index seen
For each index i (going right to left):
- Compute target = reverse(nums[i])
- If target in map, we found a j > i with nums[j] == reverse(nums[i])
- Update minimum distance: map[target] - i
- Store nums[i] -> i in map (smallest index for this value)

Why Right to Left?

We want the smallest j > i. By going right to left and storing the smallest index seen for each value, when we process i, the map contains the smallest j > i for any value.

Complexity

Time: O(n × d) where d = max digits ≈ 10
Space: O(n)

Edge Cases

No mirror pairs → return -1
Palindrome numbers (reverse = self) need i < j with same value
Numbers with trailing zeros (120 → 21)

Code

from typing import List


class Solution:
    def minDistance(self, nums: List[int]) -> int:
        """
        3761. Minimum Absolute Distance Between Mirror Pairs
        Time: O(n)
        Space: O(n)
        """
        def reverse(x: int) -> int:
            return int(str(x)[::-1])

        n = len(nums)
        min_dist = float('inf')

        # Map: value -> smallest index seen (processing right to left)
        value_to_idx = {}

        for i in range(n - 1, -1, -1):
            target = reverse(nums[i])

            # Check if target exists at some j > i
            if target in value_to_idx:
                min_dist = min(min_dist, value_to_idx[target] - i)

            # Store this value with current index
            value_to_idx[nums[i]] = i

        return min_dist if min_dist != float('inf') else -1

import java.util.*;

/**
 * 3761. Minimum Absolute Distance Between Mirror Pairs
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int minDistance(int[] nums) {
        int n = nums.length;
        int minDist = Integer.MAX_VALUE;

        // Map: value -> smallest index seen (processing right to left)
        Map<Long, Integer> valueToIdx = new HashMap<>();

        for (int i = n - 1; i >= 0; i--) {
            long target = reverse(nums[i]);

            // Check if target exists at some j > i
            if (valueToIdx.containsKey(target)) {
                minDist = Math.min(minDist, valueToIdx.get(target) - i);
            }

            // Store this value with current index
            valueToIdx.put((long) nums[i], i);
        }

        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }

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