How to find distance between adjacent elements in an array.

algorithm
array
data-structure
sorting

#1

Given an array as input A[0,1,2,3…N], in this array two elements A* and A[j] are said to be adjacent if there is no element in range (A*,A[j]) i.e, if A*=1 and A[j]=5 then A* 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)


#2

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

abs(3-2)=1

abs(1-3)=2

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


#3

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.


#4

@spinovations

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.


#5

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
so,

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

(0,1)=max(8,5)-min(4,2)=6

(1,2)=max(5,7)-min(2,1)=6

ans = 6


#6

@spinovations

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


#7

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


#8

@ronrogers

Can you please elaborate more on implementation details.