How to Find the Minimum Mirror Pair Distance in an Array

Have you ever encountered an algorithm problem where you need to find pairs of numbers that are "mirrors" (reversals) of each other?

Recently, I was working on an interesting array problem: Finding the minimum distance between two indices containing mirror pairs. For example, 12 and 21 are mirror pairs. If they appear in an array, we want to find the shortest distance between their indices.

In this post, I'll walk you through an efficient Java solution that solves this problem in a single pass using a HashMap.

The Problem

Given an integer array nums, find the minimum distance between two indices i and j such that nums[i] is the reversed version of nums[j]. If no such pair exists, return -1.

The Solution

Here is the complete Java solution:

class Solution {
    public int minMirrorPairDistance(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int ans = Integer.MAX_VALUE;

        for(int i = 0; i < nums.length; i++){
            // If the current number matches a previously stored reversed number
            if(map.containsKey(nums[i])){
                ans = Math.min(ans, Math.abs(i - map.get(nums[i])));
            }
            // Store the reverse of the current number and its index
            map.put(reverse(nums[i]), i);
        }

        if(ans == Integer.MAX_VALUE){
            return -1;
        }
        return ans;
    }

    // Helper method to reverse an integer
    public int reverse(int number){
        int num = 0;
        while(number != 0){
            int digit = number % 10;
            num = (num * 10) + digit;
            number = number / 10;
        }
        return num;
    }
}

How It Works: A Step-by-Step Breakdown

Instead of using a brute-force approach with nested loops (which would result in an O(N²) time complexity), we can optimize this to a single pass using a HashMap.

Here is the clever part of the logic: We don't store the actual numbers in the map; we store their reversed versions.

1. Initialization: We initialize a HashMap to keep track of numbers and their indices, and a variable ans set to Integer.MAX_VALUE to track the minimum distance.
2. Iterating through the array: As we loop through nums, we check if the current number (nums[i]) exists as a key in our map.
3. Calculating Distance: If it does exist, it means we previously encountered a number whose reverse is equal to our current number! We calculate the distance i - map.get(nums[i]) and update ans if this distance is smaller than our current minimum.
4. Populating the Map: Before moving to the next element, we reverse the current number using our reverse() helper method and store it in the map along with its index i.

Let's look at a Dry Run

Imagine our array is nums = [12, 45, 21, 54].

• i = 0 (nums[0] = 12): Map is empty. We reverse 12 to get 21. We put <21, 0> in the map.
• i = 1 (nums[1] = 45): Map doesn't contain 45. We reverse 45 to get 54. We put <54, 1> in the map.
• i = 2 (nums[2] = 21): Map contains 21! It was put there by 12 at index 0. The distance is 2 - 0 = 2. We update ans = 2. We reverse 21 to get 12, and put <12, 2> in the map.
• i = 3 (nums[3] = 54): Map contains 54! It was put there by 45 at index 1. The distance is 3 - 1 = 2. ans remains 2. We reverse 54 to get 45, and put <45, 3> in the map.

Result: The method correctly returns 2.

Complexity Analysis

• Time Complexity: O(N). We iterate through the array of size N exactly once. Reversing each integer takes constant time O(1) because the maximum number of digits in a 32-bit integer is 10. HashMap operations (put and get) also take O(1) time on average.
• Space Complexity: O(N). In the worst-case scenario (where no mirror pairs exist), we will store all N elements in the HashMap.

Conclusion

Using a HashMap is a fantastic way to turn a slow, nested-loop solution into a fast, linear one. By proactively storing the reversed targets we are looking for, we make checking for pairs incredibly simple and efficient.

Have you solved any similar array pairing problems recently? Let me know in the comments!