Binary Search to Find Next Greater Element III

The solution to this problem boils down to finding the next greater element to N in a sorted list. Binary Search is the best mechanism here. Steps:

1/ For each element, create a sorted list of its indexes. Store in a hash table for quick access

2/ Create a helper function to find the reverse of a number (in LogN)

3/ Create a helper function to do the Binary Search and find the next greater index

Code is down below, cheers, ACC.

Minimum Absolute Distance Between Mirror Pairs - LeetCode

ou 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​​​​​​​

 

---

Seen this question in a real interview before?

1/5

Yes

No

Accepted

12,963/32.3K

Acceptance Rate

40.1%

public class Solution {
    public int MinMirrorPairDistance(int[] nums)
    {
        Hashtable numToListIndexes = new Hashtable();
        for (int i = 0; i < nums.Length; i++)
        {
            if (!numToListIndexes.ContainsKey(nums[i])) numToListIndexes.Add(nums[i], new List());
            List list = (List)numToListIndexes[nums[i]];
            list.Add(i);
        }

        int retVal = Int32.MaxValue;
        for (int i = 0; i < nums.Length; i++)
        {
            int rev = ReverseNumber(nums[i]);
            if (numToListIndexes.ContainsKey(rev))
            {
                List sortedList = (List)numToListIndexes[rev];
                retVal = Math.Min(retVal, MinDistBinarySearch(i, sortedList));
            }
        }

        return (retVal == Int32.MaxValue) ? -1 : retVal;
    }

    private int ReverseNumber(int n)
    {
        int rev = 0;

        while (n > 0)
        {
            rev = 10 * rev + n % 10;
            n /= 10;
        }

        return rev;
    }
    private int MinDistBinarySearch(int target, List sortedList)
    {
        int left = 0;
        int right = sortedList.Count - 1;

        while (left < right)
        {
            int mid = (left + right) / 2;
            if (sortedList[mid] == target)
            {
                left = mid;
                break;
            }
            if (sortedList[mid] > target) right = mid - 1;
            else left = mid + 1;
        }

        while (left < sortedList.Count && sortedList[left] <= target)
            left++;

        if (left >= sortedList.Count) return Int32.MaxValue;
        return sortedList[left] - target;
    }
}