Given an array A, find its size-K minimum array

Q.  Given an array A of n numbers, design a method to generate array B such that B[i] is the minimum of numbers k preceding numbers ( A[i], A[i-1], ..., A[i-k+1] ).


Hint: Use a queue of size K

A running example:

Input Array: A={3, 56, 48, 12, 2, 51,10, 14}
Queue Q if size 4   
Output Array: minArray[A.length]

i = 0,  Q= {3}, min:3, minArray={3}
i = 1,  Q = {3, 56}, min:3, minArray={3,3}
For i=1, we append A[1] to queue Q. We need to determine if the new element A[1] is minimum or a previous element is minimum.  Starting from the head of the Q, we compare A[1]  with each element Q[j] where j < i. If Q[j] > A[i], we remove it. We continue this till we get an element Q[j] such that Q[j] <= A[i].

i = 2, Q = {3,56,48}, min: 3, minArray={3,3, 3}
i = 3, Q ={3,56,48,12}, min: 3, minArray = {3, 3, 3,3}
i = 4, Q = {2}, min: 2, minArray={3, 3, 3, 3, 2}
For i = 4,  queue Q is already of size 4. So we remove the first element from the head of the Q. Then, we append A[4] to Q. We determine the next minimum element by comparing A[4] with other  elements in the queue Q[j], j < i, starting from the head.  If Q[j] > A[i], we remove it. We continue this till we get an element Q[j] such that Q[j] <= A[i].

i = 5, Q={2, 51}, min: 2, minArray={3 , 3, 3, 3, 2, 2}
i = 6, Q= {2,51,10}, min: 2, minArray={3, 3, 3, 3, 2, 2, 2}
i = 7, Q={2, 51, 10, 14}, min:2, minArray =  {3, 3, 3, 3, 2, 2, 2, 2}