Minimum Distances HackerRank Problem

Task :- To calculate minimum distance between two equal/same elements.

For eg:- arr= [3, 2, 1, 2, 3], the two valid answers are 4(for value 3) and 2(for value 2) and the minimum of them is 2. So the answer is 2.

Brute Force Approach :- For each element, we can check all elements in front to check whether they are equal or not, and if they are equal we can update minimum if needed.

Simple way to do this is to use two for loops.The outer for loop with iterator i will iterate from 0 to n-2 and the inner for loop will iterate from i+1 to n-1 (where n is length of array) and in each iteration we check whether values at i th index and j th index are same or not. If they are the same we can update the minimum if the distance between them is smaller than the current minimum.

The time complexity for this approach is O(N²) since we are traversing linearly in both of the loops.

Brute Force Code :-

Better Approach :- We can use HashMap/Dictionary to store the indexes of each element and then using them we calculate the distance and update the minimum whenever required. So we create a dictionary with ‘value of the element’ as key and value would be a list of indexes of that particular value. For an element if there are no matching values there would be only one value in the list and length of list would be greater than 1 if there are matching pairs and now we can traverse this list to find distance between them.

For eg :- The dictionary for the above example would look like :

{

‘1’ : [ 2 ] ,

‘2’ : [ 1 , 3 ] ,

‘3’ : [ 0 , 4 ]

}

Note :- If there are more than two occurrences of an element the indices appended in the list would be in sorted order and also we only need to check the distance with the previous occurrence of the element.

For eg: Let’s say for element 2 we have 3 occurencences at [ 1 , 4 , 6 ].

We only need to consider the distance between 1&4, 4&6 and not 1&6 as the distance would surely be greater than the other two distances.

The time complexity of this approach is O(N) and space complexity is also O(N).

Note :- After making the dictionary we are still traversing N elements so time complexity is O(N) and not O(N²).

Code :-

Efficient Approach :- Since for an element we are only interested in last index at which the same element is present there is no need of keeping all the indexes in a list as value, we can only put one value which would be the last occurrence of that element and we calculate and update the minimum in one go only.

The time complexity of this approach is O(N) and space complexity is O(K) where K is the number of distinct elements in the array.

Space complexity would be O(N) in the worst case complexity when all elements are distinct.

Efficient Code :-

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store