Asked in Amazon | Find the shortest subarray whose first and last elements differ by "1" in O(N)

Question

Expected Time Complexity : O(N) , where 'N'  is the size of the array .

1<=A[i]<=1000000

1<=N<=100000

Example :

6 100 200 400 10000 5 5 300

Output : 6 ( {6,100,200,400,10000,5} is the largest subarray of length "6" whose first and last element differ by 1) }

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

Answer 1

Algorithm

• Use haskmap to store the latest index of elements

• iterate over array

  • if element+1 or element -1 is present in hashmap

    • if(element+1 is present) 
      then update ans = min( ans , index-map[element+1]+1)

    • if(element-1 is present) 
      then update ans = min( ans , index-map[element-1]+1)

  • map[element] = index

let me know some TC where it fails