Interview Question
Country: United States
can u please explain how O(n) solution does exist with extra memory of size k........as per my thought in any case you need the complexity of ((n-k)+1)*k
We need a deque with following O(1) operations :
push_front(), pop_front(), pop_back()
1) The last element of deque will always hold the minimum element in each step( each step will give minimum for ith subarray ).
2) Element will be inserted in front only.
Suppose you have some elements in deque such that last element is minimum for subarray a[i-k] to a[i-1]. You need to find the minimum for subarray a[i-k+1] to a[i]
a) Pop all elements from front which are greater than a[i]
b) Pop all elements from back which have index less than equals to i-k
c) Push a[i] to front
d) Store last element as minimum of subarray a[i-k+1] to a[i]
Repeat a,b,c,d for all i
As all elements are inserted and deleted once only => O(n)
@Cerberuz: How will you do b) above efficiently? You might be inserting and deleting each element only once, but doesn't b) involve a linear search (O(k) every time you do this, which will give you O(nk) overall for this algo)?
Solution is indeed O(n).
All the elements which have index less than equals to i-k will be consecutive in the end of the deque.
*Any element with index < i will always be inserted before any other element which have index >= i.
I see what you're doing. I didn't think you were enforcing order by index in the deque, but your last comment clarified it for me.
+1 from me.
Cerberuz, could you clarify how this accomplishes the look-ahead aspect of the problem? Your solution seems to solve for min(A[i-k+1], A[i-k+2],...,A[i]), but not for min(A[i], A[i+1],...,A[i+k]).
Am I misunderstanding some aspect of your solution?
I guess a reverse traversal with the last k-1 elements preloaded into the array would be the algorithm you describe, and begin with A[A.Count() - k]. Still, confused me for a minute there.
Yeah, in the problem those without k comparisons to make are dropped (so B.Length = A.Length - k + 1). I don't see how this can be a lookahead algorithm without a backwards traversal, since you're relying on the history of the search.
@Patrick, I am not able to get you, do you have a test case where the algorithm fails or you want to say that its not O(n) ?
Your algorithm seems (again, I might be misunderstanding) to use a lookback, and since you didn't mention starting params I assume you'd go with the beginning, and assign B[i] to the value found for A[i]. I was just confused because you didn't describe the initialization or mapping between B and A. For example, with the array:
{5,1,3,4,2,7} with k=3, the output I understand from your algo would be {5, 1, 1, 1,2,2}, where the intended output is {1,1,2,2}. It's a small bug, in that you add on k-1 elements to the beginning. If I missed some part where you pre-process k-1 elements then begin to copy to B (or another way of handling this) then I take it all back. :)
Does that make sense?
Firstly, i am not using array B for storing result ( result is stored inplace in the given array ).
e.g 5,1,3,4,2,7
Initialization : a[0] = minimum of ( a[0] to a[k-1] ) = 1
deque = 3->1 ( insert elements from min element till a[k-1] )
Now proceed from a[3] and fill values from a[1]
deque = 4->3->1 : a[1] = 1
deque = 2 : a[2] = 2
deque = 7->2 : a[3] = 2
// Worst Case O(nk) if array are already sorted.
void findMin(int *arr, int k , int len)
{
int i,j,min=INT_MAX, index =0,l=0;
for(i=0; i<=len-k; i++)
{
if(index > i && index < i+k)
{
if(arr[i+k-1] < min)
{
min = arr[i+k-1];
index = i+k-1;
}
}
else
{
min = INT_MAX;
for(j=i; j<i+k ;j++)
if(arr[j] <= min)
{
min = arr[j];
index = j;
}
}
printf("%d ",min);
}
}
The problem statement said you must do it in less than O(nk), but by your own acknowledgment, it's O(nk).
I have given you +1 despite the fact that you are supposed to return the output vector, and that too without extra space..
@Cerberuz: i didnt understand exactly what is happening in here in the deque. plz can u elaborate.
For each subarray of type a[i-k+1] to a[i] you have to maintain deque such that it contains elements less than equals to a[i] in non increasing order from front.
So in each step you throw out all elements from front which are greater than a[i] and elements from back which are not in current window.
As deque is sorted in non increasing order, minimum element of sub array will always be at its end.
@cerberuz I think the below mentioned code will explain properly what cerberuz proposed......what do you say cerberuz?
package programs;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class program1 {
public static void BuildArray(ArrayList<Integer> A,int k)
{
ArrayDeque<Integer>D = new ArrayDeque<Integer>();
ArrayList<Integer> L = new ArrayList<Integer>();
int q = k;
for(int i=0;i<A.size();i++)
{
if(D.isEmpty())
{
D.addFirst(i);
if(i==(q-1))
{
q++;
L.add(A.get(D.getLast()));
}
else
continue;
}
else
{
for(Iterator itr = D.iterator();itr.hasNext();)
{
int num = ((Integer)itr.next()).intValue();
if(A.get(num)>A.get(i))
{
D.removeFirst();
}
else
break;
}
for(Iterator itr = D.descendingIterator();itr.hasNext();)
{
int w = q-k-1;
int num = ((Integer)itr.next()).intValue();
if(num<=w)
{
D.removeLast();
}
else
break;
}
D.addFirst(i);
if(i==(q-1))
{
q++;
L.add(A.get(D.getLast()));
}
else
continue;
}
}
System.out.print("Now the array is: ");
for(int i=0;i<L.size();i++)
{
System.out.print(L.get(i)+" ");
}
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
ArrayList<Integer> D = new ArrayList<Integer>();
System.out.println("Please enter the no. of array elements: ");
int l = in.nextInt();
for(int i=0;i<l;i++)
{
D.add(in.nextInt());
}
System.out.println("Please enter window length: ");
//int k = in.nextInt();
BuildArray(D,in.nextInt());
}
}
O(n) solution with extra memory for array of size k exists. ( i am assuming we have to do it inplace without using memory for array B )
- Cerberuz September 09, 2012