Skip to content

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}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
}

Comments