Given An Array, find the minimum distance between any pair of equal elements in the array.

Problem Statement

Given An Array, find the minimum distance between any pair of equal elements in the array, return -1 if there is no equal elements.

Example

Input : 1 2 3 4 10 Expected output : -1

Example

Input : 7 1 3 4 1 7 Expected output : 3

Here is a link to the problem on Hackerrank.

Approach

First we have to find the indices of where there are duplicates, that is a list of all the indices where a particular element occurs, now we have to find the minimum absolute difference between those indices.

Pro Tip : If the indices are in sorted fashion, we can get that minimum in O(n)

We also need a way to check if we have already seen that element before or not. HashMap is the answer to this.

Now we can have a structure like this, a hashmap where the key is the element and the value is the list of indices where that element occurs in the array.

We traverse through the array, check if the element is present in the array and if yes, then we simply add that index to the list corresponding to that element, otherwise insert that element in the hashmap and the value corresponding to it will be a list with only one element i.e the first index where this element is present in the array.

Once this structure is ready we simply have to traverse through all the lists in the hashmap and then calculate the difference between adjacent elements, and update the variable which contains the minimum difference spotted till now.

Solution

Below is the python code which passed all test cases.

def minimumDistances(a):
    hm = {}
    for i in range(len(a)):
        if hm.get(a[i]):
            hm.get(a[i]).append(i)
        else:
            hm[a[i]] = [i]
    res = 100000
    for values in hm.values():
        for i in range(len(values)-1):
            x = abs(values[i]-values[i+1])
            if x < res:
                res = x
    return res if res != 100000 else -1

Key Points To Remember

• HashMap when you have to remember previous occurence and you need O(1) lookups. ✔
• Sorting, think if sorting the array would help you in some way or not. ✔

👏 Congrats! You just learned a frequently asked interview question.👏