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());
}
}
