LogoKode$word
LeetCode 3761 Minimum Absolute Distance Between Mirror Pairs | Java HashMap Solution
LeetCode 3761 Minimum Absolute Distance Between Mirror Pairs | Java HashMap Solution

LeetCode 3761 Minimum Absolute Distance Between Mirror Pairs | Java HashMap Solution

Solve LeetCode 3761 using an optimized HashMap approach. Learn intuition, naive vs optimized solution, and Java code with detailed explanation.

29 views
0
0
Github icon
Github icon
Listen to articleAudio version

Introduction

Some problems look simple at first—but hide a clever trick inside.

LeetCode 3761 – Minimum Absolute Distance Between Mirror Pairs is one such problem. It combines:

  1. Number manipulation (digit reversal)
  2. Hashing
  3. Efficient searching

If approached naively, this problem can easily lead to O(n²) time complexity—which is not feasible for large inputs.

In this article, we will walk through:

  1. Problem intuition
  2. Naive approach (and why it fails)
  3. Optimized HashMap solution
  4. Step-by-step explanation
  5. Clean Java code with comments

🔗 Problem Link

LeetCode: Minimum Absolute Distance Between Mirror Pairs

To gain a deeper understanding of the problem, it is highly recommended that you review this similar problem Closest Equal Element Queries here is the link of the article. Both cases follow a nearly identical pattern, and studying the initial example will provide valuable context for the current task.

Problem Statement

You are given an integer array nums.

A mirror pair (i, j) satisfies:

  1. 0 ≤ i < j < nums.length
  2. reverse(nums[i]) == nums[j]

👉 Your task is to find:

The minimum absolute distance between such pairs

If no mirror pair exists, return -1.

Examples

Example 1

Input:

nums = [12, 21, 45, 33, 54]

Output:

1

Explanation:

  1. (0,1) → reverse(12) = 21 → distance = 1
  2. (2,4) → reverse(45) = 54 → distance = 2
  3. ✔ Minimum = 1

Example 2

Input:

nums = [120, 21]

Output:

1

Example 3

Input:

nums = [21, 120]

Output:

-1

Key Insight

The core idea is:

Instead of checking every pair,
store reversed values and match on the fly.

❌ Naive Approach (Brute Force)

Idea

  1. Check all pairs (i, j)
  2. Reverse nums[i]
  3. Compare with nums[j]

Complexity

  1. Time: O(n²) ❌
  2. Space: O(1)

Problem

With n ≤ 100000, this approach will definitely cause TLE.

✅ Optimized Approach (HashMap)

Intuition

While iterating through the array:

  1. Reverse the current number
  2. Check if this number was already seen as a reversed value
  3. If yes → we found a mirror pair

Key Trick

Instead of storing original numbers:

👉 Store reversed values as keys

This allows instant lookup.

Java Code (With Detailed Comments)

import java.util.*;

class Solution {

// Function to reverse digits of a number
public int reverse(int m) {
int rev = 0;

while (m != 0) {
int dig = m % 10; // extract last digit
m = m / 10; // remove last digit
rev = rev * 10 + dig; // build reversed number
}

return rev;
}

public int minMirrorPairDistance(int[] nums) {

// Map to store reversed values and their indices
HashMap<Integer, Integer> mp = new HashMap<>();

int min = Integer.MAX_VALUE;

for (int i = 0; i < nums.length; i++) {

// Check if current number exists in map
// Meaning: some previous number had reverse equal to this
if (mp.containsKey(nums[i])) {

// Calculate distance
int prevIndex = mp.get(nums[i]);
min = Math.min(min, Math.abs(i - prevIndex));
}

// Reverse current number
int revVal = reverse(nums[i]);

// Store reversed value with index
mp.put(revVal, i);
}

// If no pair found, return -1
return min == Integer.MAX_VALUE ? -1 : min;
}
}

Step-by-Step Dry Run

Input:

nums = [12, 21, 45, 33, 54]

Execution:

IndexValueReverseMap CheckAction
01221not foundstore (21 → 0)
12112founddistance = 1
24554not foundstore (54 → 2)
33333not foundstore (33 → 3)
45445founddistance = 2

👉 Minimum = 1

Complexity Analysis

Time Complexity

  1. Reversing number → O(digits) ≈ O(log n)
  2. Loop → O(n)

👉 Overall: O(n)

Space Complexity

  1. HashMap stores at most n elements

👉 O(n)

Why This Approach Works

  1. Avoids unnecessary pair comparisons
  2. Uses hashing for constant-time lookup
  3. Processes array in a single pass

Key Takeaways

  1. Always think of hashing when matching conditions exist
  2. Reversing numbers can convert the problem into a lookup problem
  3. Avoid brute force when constraints are large
  4. This is a classic “store & check” pattern

Common Interview Pattern

This problem is similar to:

  1. Two Sum (hashing)
  2. Reverse pairs
  3. Matching transformations

Conclusion

The Minimum Absolute Distance Between Mirror Pairs problem is a great example of how a simple optimization (using a HashMap) can reduce complexity from O(n²) → O(n).

Understanding this pattern will help you solve many similar problems involving:

  1. Transformations
  2. Matching conditions
  3. Efficient lookups

Frequently Asked Questions (FAQs)

1. Why store reversed value instead of original?

Because we want to quickly check if a number matches the reverse of a previous number.

2. What if multiple same reversed values exist?

The map stores the latest index, ensuring minimum distance is considered.

3. Can this be solved without HashMap?

Yes, but it will result in inefficient O(n²) time.

Related Articles

LeetCode 3488 — Closest Equal Element Queries: A Complete Walkthrough from Brute Force to Optimal

LeetCode 3488 — Closest Equal Element Queries: A Complete Walkthrough from Brute Force to Optimal

Solve LeetCode 3488 Closest Equal Element Queries using HashMap and Binary Search. Learn intuition, naive vs optimized approach, circular distance logic, and Java solution with detailed explanation.

Read Article
LeetCode 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

LeetCode 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

Step-by-Step Explanation with Optimized Approach and Time Complexity Analysis

Read Article
Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Optimizing from O(n) Linear Scan to O(log n) Binary Search

Read Article
Intersection of Two Arrays

Intersection of Two Arrays

LeetCode Question 349

Read Article
Ai Assistant Kas