Consider the array 3 5 7 6 3.
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.
Output:
(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)
(0,1) (1,2) (1,3) (2,3)
Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= 2.
Output:
(0,0) (1,1) (2,2) (3,3) (4,4) (5,5)
(0,1) (1,2) (1,3) (2,3)
Obviously the brute force is to look up all possible sublists (O(n^2) and find min and max of each (O(n)) and check then print out result. The output result step will always take O(n), let's forget about that and focus on the sublists finding step. So this is O(n^3).
Further optimizing is to use sliding or crawling window in stead of blindly checking all possible sublists , since we can shrink window once the sublist is not qualified, and expand the window after qualified sublist if found. That is O(n^2).
So can we find min/max in each sliding window in O(1) time? If we can, that will further reduce the time complexity to O(n).
There is an incredible post on careercup.com about the solution. http://www.careercup.com/question?id=5090693043191808. All credits should go to the author in the discussion thread.
Let's focus on find the minimum. Actually the problem essentially comes down to a data structure called minimum queue, which can find minimum value in the FIFO queue in O(1) time at any given time. To implement this kind of queue, we will use another data structure called minimum stack, which can find minimum value in the LIFO order in O(1) time. Combining a queue implementation with two stacks, we have our minimum queue implementation!
The take-home message of this problem is all of complicated coding problems are built on top of fundamentals like data structure (list, stack, queue, tree, hash) or search algorithms (binary search). There are thousands of hard coding problems, but there are only dozens or few hundreds of data structures and algorithms.
public static List<Pair> countSlices(int[] numbers, int k){
if(numbers==null)
return null;
List<Pair> list = new ArrayList<Pair>();
//p0, p1 defines the sliding windows
int p0=0, p1=0, len = numbers.length;
MQueue q = new MQueue();
q.enqueue(numbers[p1]);
while(p0<len && p1<len && p0<=p1){
int min = q.min();
int max = q.max();
if(max-min<=k){
for(int p=p1; p>=p0; p--){
list.add(new Pair(p1, p));
}
p1++;//expand sliding window
if(p1<len) q.enqueue(numbers[p1]);
}else{
p0++;//shrink sliding window
q.dequeue();
}
}
return list;
}
static class Pair{
int i; int j;Pair(int i1, int j1){i = i1; j = j1;}
@Override
public String toString(){return "("+i+"-"+j+")";
}
}
//a stack node which contains min and max of all underlying elements
static class MNode {
Integer i, min, max;
MNode(int i, int max, int min){this.i = i;this.max=max; this.min=min;}
}
//a stack(LIFO) can track min and max of all elements in amortized O(1) time
static class MStack {
Stack<MNode> s = new Stack<MNode>();
public boolean isEmpty(){
return s.isEmpty();
}
public int min(){
if(s.isEmpty())
return Integer.MAX_VALUE;
return s.peek().min;
}
public int max(){
if(s.isEmpty())
return Integer.MIN_VALUE;
return s.peek().max;
}
public void push(int i){
int max=Math.max(i, max());
int min=Math.min(i, min());
s.push(new MNode(i, max, min));
}
public int pop(){
return s.pop().i;
}
}
//a queue(FIFO) can track min and max of all elements in amortized O(1) time
static class MQueue{
MStack s_new = new MStack(), s_old = new MStack();
public void enqueue(int i){
s_new.push(i);
}
public int dequeue(){
if(s_old.isEmpty()){
while(!s_new.isEmpty()){
s_old.push(s_new.pop());
}
}
return s_old.pop();
}
public boolean isEmpty(){
return s_new.isEmpty() && s_old.isEmpty();
}
public int min(){
return Math.min(s_new.min(), s_old.min());
}
public int max(){
return Math.max(s_new.max(), s_old.max());
}
}
I try to figure out if it is an O(1) solution. I think like this. In average, each element enqueue and dequeue take 2 push and 2 pop. So it is O(1) solution. am i right?
ReplyDeleteinsert/delete by amortized is O(1), findmin/findmax is O(1)
DeleteOne thing you can improve is that you use another stack to store the max values instead of storing it every time. It is (max, number). When there is a new_max, then we put (new_max, 1) in the stack. When there is another same new_max, then we update with (new_max, 2). You use this structure for your s_old.
ReplyDeleteAnd you can use only 2 integers for max, min for your new_list.
i can use reference in stead of storing value. or as you said another stack to store the max, but i also need another stack to store min. So I found to use one stack to store min and max is the simplest. Then on top of two stacks, i create the queue. which support enqueue and dequeue, findmin and findmax all in O(1)
DeleteI mean when there are only enqueue and dequeue operations, regardless that If you want removeLast function:)
ReplyDeletethis is FIFO queue. not double-end queue like Dequeue in java
Delete