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
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
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.
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
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
@arpit728 A simple queue or a vector(or an array) may be enough to store the required values.