## 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.