Interview Question
Country: India
Interview Type: Written Test
If we are starting from the first element on right then the B[1] = A[1]. now at every step we are adding on more element to compute the next min element.
-Let say we are trying to evaluate B[x] where x is in range i =< x <= n-k+1.
-B[x-1] already contains the min among A[i] - A[x-1].
-Now we compare A[x] to B[x-1].
-If A[x] < B[x-1] then B[x] = A[x] else B[x] = B[x-1].
-Itereate over the entire list in similar way.
I guess complexity will be O(n) and no extra space is required except the new array that we are creating.
We need K variables to find minimum of K elements at any time.
- Learner May 12, 2012Algo: i=0, K=user_input
Repeat the following steps from i=0 to i=N-K+1
1) Start traversing array from index i, moving towards right, considering K elements at a time.
2) Find min of K elements i.e A[i+0] to A[i+K-1]. Complexity=O(K)
3) Update B[i] with value as in step (2).
4) Increment i.