Welcome to Subscribe On Youtube

3761. Minimum Absolute Distance Between Mirror Pairs

Description

You are given an integer array nums.

A mirror pair is a pair of indices (i, j) such that:

• 0 <= i < j < nums.length, and
• reverse(nums[i]) == nums[j], where reverse(x) denotes the integer formed by reversing the digits of x. Leading zeros are omitted after reversing, for example reverse(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 distance abs(0 - 1) = 1.
• (2, 4) since reverse(nums[2]) = reverse(45) = 54 = nums[4], giving an absolute distance abs(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 <= 105
• 1 <= nums[i] <= 109​​​​​​​

Solutions

Solution 1: Hash Table

We can use a hash table $\textit{pos}$ to record the last occurrence position of each reversed number.

We first initialize the answer $\textit{ans} = n + 1$, where $n$ is the length of the array $\textit{nums}$.

Next, we iterate through the array $\textit{nums}$. For each index $i$ and its corresponding number $x = \textit{nums}[i]$, if the key $x$ exists in $\textit{pos}$, it means there exists an index $j$ such that $\textit{nums}[j]$ reversed equals $x$. In this case, we update the answer to $\min(\textit{ans}, i - \textit{pos}[x])$. Then, we update $\textit{pos}[\text{reverse}(x)]$ to $i$. Continue this process until we finish iterating through the entire array.

Finally, if the answer $\textit{ans}$ is still equal to $n + 1$, it means no mirror pair exists, and we return $-1$; otherwise, we return the answer $\textit{ans}$.

The time complexity is $O(n \times \log M)$, where $n$ is the length of the array $\textit{nums}$, and $M$ is the maximum value in the array. The space complexity is $O(n)$, which is used to store the hash table $\textit{pos}$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int minMirrorPairDistance(int[] nums) {
          int n = nums.length;
          Map<Integer, Integer> pos = new HashMap<>(n);
          int ans = n + 1;
          for (int i = 0; i < n; ++i) {
              if (pos.containsKey(nums[i])) {
                  ans = Math.min(ans, i - pos.get(nums[i]));
              }
              pos.put(reverse(nums[i]), i);
          }
          return ans > n ? -1 : ans;
      }
  
      private int reverse(int x) {
          int y = 0;
          for (; x > 0; x /= 10) {
              y = y * 10 + x % 10;
          }
          return y;
      }
  }
  
  

• class Solution {
  public:
      int minMirrorPairDistance(vector<int>& nums) {
          int n = nums.size();
          int ans = n + 1;
          unordered_map<int, int> pos;
          auto reverse = [](int x) {
              int y = 0;
              for (; x > 0; x /= 10) {
                  y = y * 10 + x % 10;
              }
              return y;
          };
          for (int i = 0; i < n; ++i) {
              if (pos.contains(nums[i])) {
                  ans = min(ans, i - pos[nums[i]]);
              }
              pos[reverse(nums[i])] = i;
          }
          return ans > n ? -1 : ans;
      }
  };
  
  

• class Solution:
      def minMirrorPairDistance(self, nums: List[int]) -> int:
          def reverse(x: int) -> int:
              y = 0
              while x:
                  v = x % 10
                  y = y * 10 + v
                  x //= 10
              return y
  
          pos = {}
          ans = inf
          for i, x in enumerate(nums):
              if x in pos:
                  ans = min(ans, i - pos[x])
              pos[reverse(x)] = i
          return -1 if ans == inf else ans
  
  

• func minMirrorPairDistance(nums []int) int {
  	n := len(nums)
  	pos := map[int]int{}
  	ans := n + 1
  	reverse := func(x int) int {
  		y := 0
  		for ; x > 0; x /= 10 {
  			y = y*10 + x%10
  		}
  		return y
  	}
  	for i, x := range nums {
  		if j, ok := pos[x]; ok {
  			ans = min(ans, i-j)
  		}
  		pos[reverse(x)] = i
  	}
  	if ans > n {
  		return -1
  	}
  	return ans
  }
  
  

• function minMirrorPairDistance(nums: number[]): number {
      const n = nums.length;
      const pos = new Map<number, number>();
      let ans = n + 1;
      const reverse = (x: number) => {
          let y = 0;
          for (; x > 0; x = Math.floor(x / 10)) {
              y = y * 10 + (x % 10);
          }
          return y;
      };
      for (let i = 0; i < n; ++i) {
          if (pos.has(nums[i])) {
              const j = pos.get(nums[i])!;
              ans = Math.min(ans, i - j);
          }
          pos.set(reverse(nums[i]), i);
      }
      return ans > n ? -1 : ans;
  }
  
  

All Problems

All Solutions