0 like 0 dislike
439 views
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
in Algorithms and Problems by Expert (17,730 points) | 439 views

1 Answer

1 like 0 dislike
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

by Expert (1,790 points)