Minimum Absolute Distance Between Mirror Pairs - Video Solutions
Minimum Absolute Distance Between Mirror Pairs | Simplest Explanation | Leetcode 3761 | MIK
Minimum Absolute Distance Between Mirror Pairs - Video Solution
Watch 10 video solutions for Minimum Absolute Distance Between Mirror Pairs, a medium level problem involving Array, Hash Table, Math. This walkthrough by codestorywithMIK has 4,251 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer array nums.
A mirror pair is a pair of indices (i, j) such that:
0 <= i < j < nums.length, andreverse(nums[i]) == nums[j], wherereverse(x)denotes the integer formed by reversing the digits ofx. Leading zeros are omitted after reversing, for examplereverse(120) = 21.
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.
Example 1:
Input: nums = [12,21,45,33,54]
Output: 1
Explanation:
The mirror pairs are:
- (0, 1) since
reverse(nums[0]) = reverse(12) = 21 = nums[1], giving an absolute distanceabs(0 - 1) = 1. - (2, 4) since
reverse(nums[2]) = reverse(45) = 54 = nums[4], giving an absolute distanceabs(2 - 4) = 2.
The minimum absolute distance among all pairs is 1.
Example 2:
Input: nums = [120,21]
Output: 1
Explanation:
There is only one mirror pair (0, 1) since reverse(nums[0]) = reverse(120) = 21 = nums[1].
The minimum absolute distance is 1.
Example 3:
Input: nums = [21,120]
Output: -1
Explanation:
There are no mirror pairs in the array.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach Overview
Problem Overview: Given an array of integers, you need the smallest absolute distance between indices i and j such that the two values form a mirror pair. A mirror pair means one value is the mathematical mirror of the other (for example x and -x). The goal is to scan the array and return the minimum |i - j| among all valid pairs.
Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)
The straightforward method checks every pair of indices. For each i, iterate through all j > i and test whether nums[i] and nums[j] are mirrors. When a mirror condition is satisfied, compute the absolute index difference and track the minimum. This approach is easy to implement but inefficient for large arrays because it performs roughly n × n comparisons. It mainly serves as a baseline and demonstrates the problem constraints clearly.
Approach 2: Hash Table Lookup (O(n) time, O(n) space)
The optimal solution uses a hash table to remember previously seen numbers and their indices while scanning the array once. When processing an element x at index i, compute its mirror value -x. A constant-time hash lookup tells you whether that mirror appeared earlier. If it exists, compute the index distance |i - prevIndex| and update the minimum distance.
This approach works because each element’s mirror relationship can be checked instantly with a hash map instead of searching the entire array. You simply iterate through the array, perform a hash lookup, and update the stored index for the current number. The algorithm runs in linear time with additional storage for the map. The mirror relationship relies on a simple math transformation (-x), which keeps the logic straightforward.
Recommended for interviews: Start by mentioning the brute force pair comparison to show you understand the definition of mirror pairs and the distance requirement. Then move quickly to the hash table approach. Interviewers expect the O(n) single-pass solution because it demonstrates familiarity with hash-based lookups and common array optimization patterns.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Useful for understanding the mirror condition or when the array size is very small |
| Hash Table Lookup | O(n) | O(n) | General case and interview-preferred solution for large arrays |