How to find distance between adjacent elements in an array.

Given an array as input A[0,1,2,3…N], in this array two elements A[i] and A[j] are said to be adjacent if there is no element in range (A[i],A[j]) i.e, if A[i]=1 and A[j]=5 then A[i] and A[j] are said to be adjacent if array doesn’t contain element in range (1,5).

Calculate the maximum possible distance j-i where j and i are indices of adjacent element in given array.

Expected time complexity: O(N logN)

Try to sort the array along with its index which will take O(N logN). Then a simple transversal of in O(N) will give you the answer.

ex. let A = [7,1,5]

sorting with index(I am doing ‘1’ based indexing here) will give you

(1,index:2), (5, index:3), (7, index:1)

now transverse the sorted list and calculate j-i and store the max



here the answer will be 2.

Please accept the solution if it solved your doubt. If there is some problem in my algo please let me know



I came across this approach, but I got stuck at for duplicate values.

suppose array after sorting becomes: 0 0 0 1 1 2 2 2

How we will handle this case.

1 Like

Use two loops: The outer loop picks all the elements of arr[] one by one. The inner loop picks all the elements after the element picked by outer loop. You can get answer from our services.Its very useful.Many academic writing resources to provide reliable writing assistance for academic assignment. Some characters must have in your mind while selecting the essay writing service.

Even if there are repeated values you can consider that while transversing.

ex. A = [2,1,2,0,1,0,2,0] (your type of example)

After sorting:

(0,idx:4),(0,idx:6), (0,idx:8),(1,idx:2),(1,idx:5),(2,idx:1), (2,idx:3),(2,idx:7)

start with first element transverse till repeated elements. Store min and max index for same elements

for 0: min:4, max:8

for 1: min:2, max:5

for 2: min:1, max:7

Observe that for each repeated number we only require max and min index.

simply max - min between two elements



ans = 6



After sorting, how do I store min and max index of every element. hashmap?

@arpit728 A simple queue or a vector(or an array) may be enough to store the required values.

1 Like


Can you please elaborate more on implementation details.