Sliding Window Maximum

January 25, 2011 in Uncategorized

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

The obvious brute force solution with run time complexity of O(nw) is definitely not efficient enough. Every time the window is moved, you have to search for a total of w elements in the window.

A heap data structure quickly comes to mind. We could boost the run time to approximately O(n lg w) (Note that I said approximately because the size of the heap changes constantly and averages about w). Insert operation takes O(lg w) time, where w is the size of the heap. However, getting the maximum value is cheap, it merely takes constant time as the maximum value is always kept in the root (head) of the heap.

As the window slides to the right, some elements in the heap might not be valid anymore (range is outside of the current window). How should you remove them? You would need to be somewhat careful here. Since you only remove elements that are out of the window’s range, you would need to keep track of the elements’ indices too.

Note that as n grows larger, the term lg w is pretty insignificant compared to n, and thus the overall complexity approximates to O(n). (Edit: In fact, the correct run time complexity should be O(n log n). If A is sorted, then the inner while loop will never run. This is due to the next element (which is larger) being pushed to the queue’s top as the new maximum. (Thanks to my readers anonymous and faircoin who pointed out this.)

You might be wondering: Is there a better way of doing this without using a heap? How about using a double-ended queue? (A linked list should be fine too)

The double-ended queue is the perfect data structure for this problem. It supports insertion/deletion from the front and back. The trick is to find a way such that the largest element in the window would always appear in the front of the queue. How would you maintain this requirement as you push and pop elements in and out of the queue?

Besides, you might notice that there are some redundant elements in the queue that we shouldn’t even consider about. For example, if the current queue has the elements: [10 5 3], and a new element in the window has the element 11. Now, we could have emptied the queue without considering elements 10, 5, and 3, and insert only element 11 into the queue.

A natural way most people would think is to try to maintain the queue size the same as the window’s size. Try to break away from this thought and try to think outside of the box. Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.

The above algorithm could be proven to have run time complexity of O(n). This is because each element in the list is being inserted and then removed at most once. Therefore, the total number of insert + delete operations is 2n.

VN:F [1.9.22_1171]
Rating: 4.8/5 (70 votes cast)
Sliding Window Maximum, 4.8 out of 5 based on 70 ratings

81 responses to Sliding Window Maximum

  1. The window moves one element at a time. So you will have to check only the last element in the window each time the window moves. Right? I dont see a point in using an extra data structure. Please explain.

    VA:F [1.9.22_1171]
    -4
    • You’re right. You just need to store the max of the prev window slide and compare with the last element after the move.

      VA:F [1.9.22_1171]
      0
      • This may be problematic if previous window is 10,5,8 and current one is 5,8,6. As you mentioned, if we only keep track of max of last window, we end up comparing 10 and 6 but answer for later case is 8.

        VA:F [1.9.22_1171]
        0
  2. @Rya:
    Try reading the problem statement again. You are required to output the largest element in the window each time the window moves. The last element in the window is not necessarily the largest element.

    VA:F [1.9.22_1171]
    0
    • do a O(w) scan to get the max.
      b.pushBack(max)
      now for(valid movement of window)
      check if the new element (a[x]) > max
      max=a[x]
      b.pushback(max);
      return b

      this is sufficient rite ??

      VN:F [1.9.22_1171]
      0
      • No, you are moving the window to the right, not expanding the window to the right, you need to consider the element “removed” by moving the window

        VN:F [1.9.22_1171]
        0
  3. Thanks for your good explanation. I am not sure why in Line 12 of your last solution you compare Q.front with i-w:

    while (!Q.empty() && Q.front() <= i-w)

    should it be compared with A[i-w]?

    VA:F [1.9.22_1171]
    +2
  4. Never mind last comment. I figured it out. The queue stores indices, not actually elements.

    VA:F [1.9.22_1171]
    0
  5. Hi 1337coder, i am wondering if you can solve this problem: if not code, maybe some very efficent algorithm. :)

    Find the k-th smallest element in the union of two sorted array.
    Given 2 sorted arrays of n elements A,B. Find the k-th smallest element in the union of A and B in O(log k) time. You can assume that there are no duplicate elements

    VA:F [1.9.22_1171]
    0
    • (not considering the base cases) compare the kth elements of both array, suppose array 1 wins then in array one search for an element weaker than the kth element in 2 nd array, suppose its at l in array one , then compare k-l th element in array 2 with the l th element in array one greater of two is kth element.
      o(logk) + 2 comparisons

      VA:F [1.9.22_1171]
      0
  6. @Anonymous:
    I assume you are asking two sorted arrays of different sizes, m and n?

    Hmm. It is obvious that you can merge both arrays and find the kth smallest in O(m+n) time.

    Since you want O(log k) time, it must be using a somewhat modified binary search. You could choose two elements Ai and Bj, such that the invariant i+j=k-1 is satisfied. Then if Ai is between Bj_1 and Bj, Ai must be the kth smallest. Else if Bj is between Ai_1 and Ai, ten Bj must be the kth smallest.

    If neither of the above cases are true, then compare Ai and Bj:
    if Ai > Bj => Bj < Ai_1
    if Ai < Bj => Ai < Bj_1

    Since Ai < Bj implies Ai < Bj_1, discard Ai and the lower portion of A. Also discard Bj and upper portion of B.

    Similar for the other case, which discards upper portion of A and lower portion of B.

    Since each step you are reducing the search space by half of A and half of B, the complexity must be O(log m) + O(log n). I don't quite sure what you mean by O(log k) time.

    I hope this algorithm is complete, I will code this out and let you know my result.

    VA:F [1.9.22_1171]
    0
    • Merge the two arrays uptil the Kth element when combining. That ways the run time complexity is O(log k).

      VA:F [1.9.22_1171]
      -1
  7. @Anonymous:
    Oh, forgot to add this:
    To maintain the invariant i+j=k-1,
    you must define A[-1] and B[-1] as -INF, and A[m] and B[n] as +INF.

    VA:F [1.9.22_1171]
    -1
  8. Very nice website, thank you so much for having this wonderful website. Really enjoyed reading your posts!!!

    VA:F [1.9.22_1171]
    0
  9. public static void printMaxWindow( int [] array, int windowSize){
    int maximum = Integer.MIN_VALUE;
    maximum = findMaximum(array, windowSize);
    System.out.println( maximum);

    for ( int i = 1; i < array.length-windowSize+1; i++){
    if ( maximum < array[i+windowSize-1]){
    maximum = array[i+windowSize-1];
    }

    System.out.println(maximum);
    }
    }

    private static int findMaximum(int [] array, int length){
    int maximum = Integer.MIN_VALUE;
    for ( int i = 0; i < length; i++){
    if ( maximum < array[i]){
    maximum = array[i];
    }

    }

    return maximum;
    }

    You should be able to do this without any additional space requirement and in order n.

    VA:F [1.9.22_1171]
    0
  10. Forgot to mention that the algo is what Rya suggested in comment 1.

    VA:F [1.9.22_1171]
    0
  11. You can easily acheive nlogn using a priority queue. You don’t have do all the work you did.

    In Java, there is a PriorityQueue that you can use. It has lgn insertions and the end always has the highest value.

    Just an FYI.

    VA:F [1.9.22_1171]
    0
  12. wat about this implementation?

    public static void main(String[] args) {
    int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
    int w = 3;
    slidingwindowmax(a,w);
    }

    private static void slidingwindowmax(int[] a, int w) {

    int max = a[0];
    int i=0;
    int j=0;
    while(i<=w && j < a.length){
    max = Math.max(max, a[j]);
    System.out.print(max);
    if(i == w){
    i = -1;
    }
    i++;
    j++;
    }
    }

    VA:F [1.9.22_1171]
    0
    • @bala… your code didn’t work properly.. and it is not linear time. For linear time find the below java program and off course this is not much complicated than the 1337c0d3r program.

      class test{
      public static void main(String[] args) {
      int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
      int w = 3;
      slidingwindowmax(a,w);
      }

      private static void slidingwindowmax(int[] a, int w) {

      int max = a[0];
      int i=0;
      int j=0;
      int count=0;
      while(count<w){
      max = Math.max(max, a[j]);
      count++;
      j++;
      if(count == w){
      System.out.println(max);
      count = 0;
      break;
      }
      }
      for(j=w;j max)? a[j]:max;
      System.out.println(max);
      }
      }
      }

      VA:F [1.9.22_1171]
      0
  13. We don’t need while loop : while (!Q.empty() && Q.front() <= i-w)

    This can simply be replaced by a if condition because every time there could be at most a single element which lies out of window of size w and we make sure if it is we remove it. No while loop is required for this.

    -Vipul

    VA:F [1.9.22_1171]
    0
    • I think you might be right. “Might” because I worked it out through my thought and I think you are right. But I couldn’t claim that it is correct yet because I haven’t verified through test cases. Thanks for your comment.

      VN:F [1.9.22_1171]
      0
      • I believe Vipul is right. When window moves, only the starting index is out of range. And Q.front() contains the index of maximal in the window. It is obvious that *(++Q.begin()) must be greater than i-w. So the while loop could be replaced with an if conditional branch.

        VA:F [1.9.22_1171]
        0
  14. HI, in the following code:

    while (p.second <= i-w) {
    Q.pop();
    p = Q.top();
    }

    Every time you move one position, you need to examine all the items in the queue. So the overall complexity still O(N)? The above code complexity is already 0(W).

    VA:F [1.9.22_1171]
    0
    • Think: What is the maximum number of elements you can pop from the queue? This is the number of elements you push to the queue right?

      VN:F [1.9.22_1171]
      0
  15. For priority queue solution, complexity is indeed O(n log n). The reason is that the max size of heap can grow to O(n) in worst case. For example, if A = {1,2,3,4,5,6,7,8,9}, line 9 – 12 never executes. On the other hand, if A = {9,8,7,6,5,4,3,2,1} heap size remains O(w) all the time.

    One more alternative solution that I propose for this problem is solving range minimum query using
    O(n log w) sized table. There are total O(n) queries, each taking O(1) time to solve. For reference, interested readers can read this tutorial
    http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

    VA:F [1.9.22_1171]
    0
    • Thanks, you are indeed correct. When A is sorted, it has the worst case of O(n log n) since the newly pushed element is the new maximum and therefore the inner while loop will never execute.

      VN:F [1.9.22_1171]
      0
  16. A simpler method for this problem.
    Only need O(1) extra space, also with time complexity O(n).

    void maxSlidingWindow(int A[], int n, int w, int B[]) {
    int imax = 0, icurmax;
    for (int i = 0; i A[imax])
    imax = i;
    }
    B[0] = A[imax];

    for (int i = 1; i A[i+w-1])?(i-1):(i+w-1);
    if (A[icurmax]>A[imax])
    imax = icurmax;
    B[i] = A[imax];
    }
    }

    VA:F [1.9.22_1171]
    +1
    • void maxSlidingWindow(int A[], int n, int w, int B[]) {
      int imax=0,icurmax;
      for (int i=0;iA[imax])
      imax = i;
      }
      B[0] = A[imax];

      for (int i=1;iA[i+w-1])?(i-1):(i+w-1);
      if (A[icurmax]>A[imax]) {
      imax = icurmax;
      }
      B[i] = A[imax];
      }
      }

      VA:F [1.9.22_1171]
      0
  17. Sorry, I don’t know why my code cannot be shown correctly.

    VA:F [1.9.22_1171]
    0
  18. Awesome!
    I learnt something about how to delete elements properly here.

    VA:F [1.9.22_1171]
    0
  19. How does the A[i] >= A[Q.back()] work??? if Q.back() is a really large number wouldnt A[Q.back] exceed the array limit , or atleast the sliding window size??

    VA:F [1.9.22_1171]
    0
  20. This seems to work:
    public class SlidingWindow {

    public static int[] getWindow(int[] a, int w) {
    int b[] = new int[a.length - w +1 ];
    b[0] = findMax(a, w, 0);
    for (int i = 1; i (length[a])
    int end = w – 1;
    if (w > a.length – start) {
    end = a.length – 1;
    }

    int max = Integer.MIN_VALUE;
    for (int i = start; i max) {
    max = a[i];
    }
    }

    return max;
    }

    public static void main(String[] args) {
    int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
    int[] b = getWindow(a, 3);
    }

    }

    VA:F [1.9.22_1171]
    0
  21. public static void main(String[] args)
    {
    int [] arr = new int [] {1, 3, -1, -3, 5, 3, 6, 7};
    int w =3;
    int max = arr[0];
    for(int i = 1; i max)
    {
    max = arr[i];
    }
    }
    System.out.println(max);
    for(int i = 1; i max)
    {
    max = arr[i+w-1];
    }
    System.out.println(max);
    }

    This solution seems to work, though i haven’t tested much.

    VA:F [1.9.22_1171]
    0
  22. public static void main(String[] args)
    {
    int [] arr = new int [] {1, 3, -1, -3, 5, 3, 6, 7};
    int w =3;
    int max = arr[0];
    for(int i = 1; i max)
    {
    max = arr[i];
    }
    }
    System.out.println(max);
    for(int i = 1; i max)
    {
    max = arr[i+w-1];
    }
    System.out.println(max);
    }
    }

    Somehow it is screwing up the code when i submit.

    VA:F [1.9.22_1171]
    0
  23. Hi 1337,

    I like your second solution very well. Thanks a lot for your posts, I learned a lot from them.

    For this problem, I have another idea of O(n) (O(4n) more exactly) time. No other data structure is needed in this solution. Can you have a look at and give me some comments? Thanks.

    //Create an array T with size of w. When window position is 0, initialize the array so that the element at position i(0<=i<w) is
    //the maximum number among the numbers from i to w-1 in current window. Then B[0]=T[0]. We know that the array T is associated with w numbers in
    //current window, and we call these w numbers as the old numbers. Then with the window moves on, new numbers will be included, and
    //old numbers will be excluded from the beginning. Assume there are i new numbers included (or i old numbers excluded),
    //the beginning i elements of the T will be updated so that they will be associated with these i new numbers and the end element in the first
    //i elements of T will be the maximum number among these i new numbers. Then, in current array T, there two parts. The first part is associated
    //with the new numbers, and the second part is associated with the old numbers. We also can directly get the maximum number among the new numbers
    //(the last element in the first part) and the maximum number among the old numbers(the first element in the second part), so that directly get
    //the maximum number in current window(the maximum number among these two maximum numbers). Once there are no old elements left for current window,
    //then we need to take all the new elements as the old elements and get the array that is associated with the old elements.
    //Pseudo codes are more persuasive.
    void winMax(int A[], int n, int w, int* B){//Avoid "address of local variable ‘B’ returned"!!!
    int T[w];
    int j = w-1;

    for(int i = 0; i = 0; j –)
    T[j] = max(A[i+j], j==w-1 ? INT_MIN : T[j+1]);
    j = 0;
    B[i] = T[0];
    }else{
    T[j] = max(A[i+w-1], j==0 ? INT_MIN : T[j-1]);
    B[i] = max(T[j], T[j+1]);
    j ++;
    }
    }
    }

    VA:F [1.9.22_1171]
    0
  24. I could not figure out how You are deleting elements which are out of range in the first solution?Can you please elaborate.

    VA:F [1.9.22_1171]
    0
  25. Hi,
    I think in the worst case the second solution will be O(wn) when the array is already sorted in descending order. Every time you want to push an element in queue you have to compare w times to maintain the queue. So the second algorithms beats the trivial algorithms in average case in that it deletes the redundant elements. I’m not sure if I am right. So I’m looking forward to get your feed back. Thanks you a lot for you great posts.

    VA:F [1.9.22_1171]
    +1
    • O(n) comes from the fact that each element will get inserted and removed at most once.

      VN:F [1.9.22_1171]
      0
      • @JQueue, when calculating the time complexity, we need to take comparison into account as well.

        VA:F [1.9.22_1171]
        0
    • in case of sorted array in descending order, each time push end a new element, only one comparison is needed. (index comparison for push front not counted)

      VA:F [1.9.22_1171]
      0
  26. one way to optimize further is to implement a double-ended queue using an array of w,

    we can use binary search to locate the correct place to insert and we can just set the head pointer to pop out the head elements

    VA:F [1.9.22_1171]
    0
  27. Hi 1337.

    I have one more solution which has run time complexity of O(n);
    Please correct me if i am wrong.

    void maxSlidingWindow(int a[], int n, int w, int b[])
    {
    int c[10];
    int max = a[0];
    for (int i=1;imax)
    max=a[i];
    }
    b[0]=max;
    int j;
    for (int i=w,j=1;imax)
    {
    max= a[i];
    }
    b[j] = max;
    }
    }

    VN:F [1.9.22_1171]
    0
  28. Amazing! you’re brilliant .. thanks a lot

    VA:F [1.9.22_1171]
    0
  29. Sliding window Maximum when shift is not 1 :

    void slidingwindowMaximum(int[] a,int[] b,int w,int shift){
    Dequeue Q;
    for(int i=0;i=A[Q.back]){
    Q.pop_back();
    }
    Q.push_back(i);
    }
    cwStart = 0;cwEnd = w-1;
    counter = 0;
    while(i<a.length){
    B[counter++]=A[Q.front()];
    cwStart+=shift;
    cwEnd+=shift;
    while(i=A[Q.back()]){
    Q.pop_back();
    }
    while(!Q.empty()&&Q.front()<cwStart){
    Q.pop_front();
    }
    Q.push_back(i);
    i++;
    }
    }
    B[counter]=A[Q.front()];

    }

    VA:F [1.9.22_1171]
    0
  30. while (!Q.empty() && Q.front() <= i-w)
    Q.pop_front();
    Should this while change to "if"?

    VA:F [1.9.22_1171]
    0
    • I think you are right. This “while” loop can be changed to “if”. But other “while” loops, including that in the priority queue method, cannot be changed to “if”.

      VN:F [1.9.22_1171]
      0
  31. No.. while should not be changed to if..since we need to remove all elements in back of queue which are less that current element.suppose queue has[11,8,7] and current elemnt is 15. then we have to remove all from back 7<15 ,8<15 , 11<15 so remove all.

    VA:F [1.9.22_1171]
    0
  32. all right I have gone through the problem statement again and again but I think I don’t understand it correctly.

    my code shouldn’t be this simple.
    where am I thinking wrong

    is this the required output

    public int[] MaxSlidingWindow(int[] a, int w)
    {
    if (a == null)
    return null;

    int i = 0;
    var b = new int[a.Length - 2];
    while(i+2 <a.Length)
    {
    b[i] = Math.Max(Math.Max(a[i], a[i + 1]), a[i + 2]);
    i++;
    }

    return b;
    }

    VA:F [1.9.22_1171]
    0
  33. can we do this problem in the following way…. or i have misunderstood the question since i am not using any complicated data structure like heap or dequeue …i am doing it using simple loop

    for(i=0;i<w;i++)
    max_num=max(max_num,arr[i]);

    B[0]=max_num;
    for(i=w,j=1;i<NUM;j++,i++)
    { max_num=max(max_num,arr[i]);
    B[j]=max_num;
    }
    for(i=0;i<j;i++)
    printf("%d ",B[i]);

    VA:F [1.9.22_1171]
    0
  34. Can we add this to OJ please?

    VN:F [1.9.22_1171]
    0
  35. //java version

    import java.util.Collections;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.List;

    public class SlidingWindow {

    public static List maxSlidingWindow(Integer[] values, Integer w){

    if(values == null || w <=0 || values.length – w + 1 < 0) return Collections.EMPTY_LIST;
    List list = new LinkedList();

    Deque q = new LinkedList();

    for(int i=0;i 0 && q.getLast() < tempData)
    q.pollLast();

    q.addLast(tempData);

    if(i+1<w) continue;

    Integer currentMax = q.getFirst();
    list.add(currentMax);

    if(values[i-w+1] == currentMax) q.removeFirst();

    }

    return list;

    }

    public static void main(String[] args) {
    Integer[] values = {1, 3 ,-1, -3, 5 ,3, 6, 7};

    List list = SlidingWindow.maxSlidingWindow(values, 3);

    for (Integer v : list) {
    System.out.print(v + ” “);

    }
    }
    }

    VA:F [1.9.22_1171]
    +1
  36. Where is the queue being initialized…W.empty will always return true…

    VA:F [1.9.22_1171]
    +1
  37. Sorry, my mistake

    VA:F [1.9.22_1171]
    0
  38. Clearly not a O(n) method. Think of a case where all elements are sorted in decreasing order.

    VA:F [1.9.22_1171]
    0
  39. I came up a O(1) space and O(n) time algorithm, please let me know if there is wrong

    VA:F [1.9.22_1171]
    0
  40. sorry, in above code the second for-loop should start from 1

    VA:F [1.9.22_1171]
    0
  41. @Chun : i think the above code DOES NOT works for numbers in descending order.
    having only the curr_max and second_max NOT sufficient since max_numbers continuously keep going out of the window.

    VA:F [1.9.22_1171]
    0
  42. definitely brilliant idea! a brilliant idea is worth a thousand lines of code. the key is to get rid of the elements both backwards and after the present max element!

    VA:F [1.9.22_1171]
    0
  43. What if the input is a stream instead of an array of fixed size?

    VN:F [1.9.22_1171]
    0
  44. Anyone knows what the B[n-w] = A[Q.front()] is for in the most original deque solution posted by 1337? Thanks a lot.

    VA:F [1.9.22_1171]
    0
  45. code without any queue

    // Type your C++ code and click the “Run Code” button!
    // Your code output will be shown on the left.
    // Click on the “Show input” button to enter input data to be read (from stdin).

    #include
    using namespace std;

    int main() {
    int a[] = {1,3,4,2,7,3,1,0,7,4,2,1,7,-1,-3,5,3,6,7};

    int aLen = 19;
    int w = 2;
    int lPtr = 0;

    int tmp[19];
    int j = 0;

    tmp[0] = a[0];
    int cntr = 0;
    for (int i = 1; i = lPtr && tmp[j] < a[i]; ) {
    j–;
    }
    tmp[++j] = a[i];
    if (++cntr < 2) {
    continue;
    }
    cout << tmp[lPtr];
    if (tmp[lPtr] == a[i - w]) {
    lPtr++;
    }

    }

    return 0;
    }

    VA:F [1.9.22_1171]
    0
  46. I like this problem. It has practical value, and the dequeue based solution is really wonderful.

    VN:F [1.9.22_1171]
    0
  47. I like this problem but don’t like the author’s answers. This problem needs to deal with insert/delete and sorted list simultaneously. I don’t believe heap or linked list is the right answer. I think the red black tree should be the most efficient way. I will provide the code in a later time.

    VN:F [1.9.22_1171]
    0
  48. here is the code using the red black tree. Apprently the time complexity is O(nlog(m)).

    VN:F [1.9.22_1171]
    -1
  49. strange. some code omitted.

    VN:F [1.9.22_1171]
    0
  50. #include
    #include
    #include

    #define INDENT_STEP 4
    enum rbtree_node_color {RED, BLACK};

    typedef struct rbtree_node_t {
    int value;
    struct rbtree_node_t* left;
    struct rbtree_node_t* right;
    struct rbtree_node_t* parent;
    enum rbtree_node_color color;
    } *rbtree_node;
    typedef rbtree_node node;
    typedef enum rbtree_node_color color;
    typedef struct rbtree_t {
    rbtree_node root;
    } *rbtree;
    typedef int (*compare_func) (int left, int right);

    static node grandparent(node n);
    static node sibling(node n);
    static node uncle(node n);
    static void verify_properties(rbtree t);
    static void verify_property_1(node root);
    static void verify_property_2(node root);
    static color node_color(node n);
    static void verify_property_4(node root);
    static void verify_property_5(node root);
    static void verify_property_5_helper(node n, int black_count, int* black_count_path);
    rbtree rbtree_create();
    static node new_node(int value, color node_color, node left, node right);
    static node lookup_node(rbtree t, int value, compare_func compare);
    static void rotate_left(rbtree t, node n);
    static void rotate_right(rbtree t, node n);
    static void replace_node(rbtree t, node oldn, node newn);
    void rbtree_insert(rbtree t, int value, compare_func compare);
    static void insert_case1(rbtree t, node n);
    static void insert_case2(rbtree t, node n);
    static void insert_case3(rbtree t, node n);
    static void insert_case4(rbtree t, node n);
    static void insert_case5(rbtree t, node n);
    void rbtree_delete(rbtree t, int value, compare_func compare);
    static node maximum_node(node root);
    static void delete_case1(rbtree t, node n);
    static void delete_case2(rbtree t, node n);
    static void delete_case3(rbtree t, node n);
    static void delete_case4(rbtree t, node n);
    static void delete_case5(rbtree t, node n);
    static void delete_case6(rbtree t, node n);
    static int compare_int(int left, int right);
    static void print_tree(rbtree t);
    static void print_tree_helper(rbtree_node n, int indent);

    color node_color(node n){
    return n==NULL ? BLACK : n->color;
    }

    node grandparent(node n) {
    assert (n != NULL);
    assert (n->parent != NULL); /* Not the root node */
    assert (n->parent->parent != NULL); /* Not child of root */
    return n->parent->parent;
    }

    node sibling(node n) {
    assert (n != NULL);
    assert (n->parent != NULL); /* Root node has no sibling */
    if (n == n->parent->left)
    return n->parent->right;
    else
    return n->parent->left;
    }

    node uncle(node n) {
    assert (n != NULL);
    assert (n->parent != NULL); /* Root node has no uncle */
    assert (n->parent->parent != NULL); /* Children of root have no uncle */
    return sibling(n->parent);
    }

    void verify_property_1(node n){
    assert(node_color(n) == RED || node_color(n) == BLACK);
    if (n==NULL) return;
    verify_property_1(n->left);
    verify_property_1(n->right);
    }

    void verify_property_2(node root){
    assert(node_color(root) == BLACK);
    }

    void verify_property_4(node n){
    if(node_color(n) == RED) {
    assert(node_color(n->left) == BLACK);
    assert(node_color(n->right) == BLACK);
    assert(node_color(n->parent) == BLACK);
    }
    if(n==NULL) return;
    verify_property_4(n->left);
    verify_property_4(n->right);
    }

    void verify_property_5_helper(node n, int black_count, int* path_black_count){
    if(node_color(n) == BLACK) {
    black_count++;
    }
    if(n==NULL){
    if (*path_black_count == -1) {
    *path_black_count = black_count;
    }else{
    assert (black_count == *path_black_count);
    }
    return;
    }
    verify_property_5_helper(n->left, black_count, path_black_count);
    verify_property_5_helper(n->right, black_count, path_black_count);
    }

    void verify_property_5(node root){
    int black_count_path = -1;
    verify_property_5_helper(root, 0, &black_count_path);
    }

    void verify_properties(rbtree t){
    verify_property_1(t->root);
    verify_property_2(t->root);
    //property 3 is implicit
    verify_property_4(t->root);
    verify_property_5(t->root);
    }

    rbtree rbtree_create(){
    rbtree t = (rbtree)malloc(sizeof(struct rbtree_t));
    t->root = NULL;
    verify_properties(t);
    return t;
    }

    node new_node(int value, color node_color, node left, node right){
    node result = (node)malloc(sizeof(struct rbtree_node_t));
    result->value = value;
    result->color = node_color;
    result->left = left;
    result->right = right;
    if(left != NULL) left->parent = result;
    if(right != NULL) right->parent = result;
    result->parent = NULL;
    return result;
    }

    node lookup_node(rbtree t, int value, compare_func compare){
    node n = t->root;
    while (n!= NULL){
    int comp_result = compare(value, n->value);
    if(comp_result == 0) {
    return n;
    }else if(comp_resultleft;
    }else {
    assert(comp_result>0);
    n=n->right;
    }
    return 0;
    }
    }

    void replace_node(rbtree t, node oldn, node newn) {
    if (oldn->parent == NULL) {
    t->root = newn;
    } else {
    if (oldn == oldn->parent->left)
    oldn->parent->left = newn;
    else
    oldn->parent->right = newn;
    }
    if (newn != NULL) {
    newn->parent = oldn->parent;
    }
    }

    void rotate_left(rbtree t, node n){
    node r = n->right;
    replace_node(t, n, r);
    n->right = r->left;
    if(r->left != NULL){
    r->left->parent = n;
    }
    r->left = n;
    n->parent = r;
    }

    void rotate_right(rbtree t, node n) {
    node L = n->left;
    replace_node(t, n, L);
    n->left = L->right;
    if (L->right != NULL) {
    L->right->parent = n;
    }
    L->right = n;
    n->parent = L;
    }

    void rbtree_insert(rbtree t, int value, compare_func compare) {
    node inserted_node = new_node(value, RED, NULL, NULL);
    if (t->root == NULL) {
    t->root = inserted_node;
    } else {
    node n = t->root;
    while (1) {
    int comp_result = compare(value, n->value);
    if (comp_result == 0) {
    free (inserted_node);
    return;
    } else if (comp_result left == NULL) {
    n->left = inserted_node;
    break;
    } else {
    n = n->left;
    }
    } else {
    assert (comp_result > 0);
    if (n->right == NULL) {
    n->right = inserted_node;
    break;
    } else {
    n = n->right;
    }
    }
    }
    inserted_node->parent = n;
    }
    insert_case1(t, inserted_node);
    verify_properties(t);
    }

    void insert_case1(rbtree t, node n) {
    if (n->parent == NULL)
    n->color = BLACK;
    else
    insert_case2(t, n);
    }

    void insert_case2(rbtree t, node n) {
    if (node_color(n->parent) == BLACK)
    return; /* Tree is still valid */
    else
    insert_case3(t, n);
    }

    void insert_case3(rbtree t, node n) {
    if (node_color(uncle(n)) == RED) {
    n->parent->color = BLACK;
    uncle(n)->color = BLACK;
    grandparent(n)->color = RED;
    insert_case1(t, grandparent(n));
    } else {
    insert_case4(t, n);
    }
    }

    void insert_case4(rbtree t, node n) {
    if (n == n->parent->right && n->parent == grandparent(n)->left) {
    rotate_left(t, n->parent);
    n = n->left;
    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
    rotate_right(t, n->parent);
    n = n->right;
    }
    insert_case5(t, n);
    }

    void insert_case5(rbtree t, node n) {
    n->parent->color = BLACK;
    grandparent(n)->color = RED;
    if (n == n->parent->left && n->parent == grandparent(n)->left) {
    rotate_right(t, grandparent(n));
    } else {
    assert (n == n->parent->right && n->parent == grandparent(n)->right);
    rotate_left(t, grandparent(n));
    }
    }

    void rbtree_delete(rbtree t, int value, compare_func compare) {
    node child;
    node n = lookup_node(t, value, compare);
    if (n == NULL) return; /* Key not found, do nothing */
    if (n->left != NULL && n->right != NULL) {
    /* Copy value from predecessor and then delete it instead */
    node pred = maximum_node(n->left);
    n->value = pred->value;
    n = pred;
    }

    assert(n->left == NULL || n->right == NULL);
    child = n->right == NULL ? n->left : n->right;
    if (node_color(n) == BLACK) {
    n->color = node_color(child);
    delete_case1(t, n);
    }
    replace_node(t, n, child);
    if (n->parent == NULL && child != NULL)
    child->color = BLACK;
    free(n);

    verify_properties(t);
    }

    void delete_case1(rbtree t, node n) {
    if (n->parent == NULL)
    return;
    else
    delete_case2(t, n);
    }

    void delete_case2(rbtree t, node n) {
    if (node_color(sibling(n)) == RED) {
    n->parent->color = RED;
    sibling(n)->color = BLACK;
    if (n == n->parent->left)
    rotate_left(t, n->parent);
    else
    rotate_right(t, n->parent);
    }
    delete_case3(t, n);
    }

    void delete_case3(rbtree t, node n) {
    if (node_color(n->parent) == BLACK &&
    node_color(sibling(n)) == BLACK &&
    node_color(sibling(n)->left) == BLACK &&
    node_color(sibling(n)->right) == BLACK)
    {
    sibling(n)->color = RED;
    delete_case1(t, n->parent);
    }
    else
    delete_case4(t, n);
    }

    void delete_case4(rbtree t, node n) {
    if (node_color(n->parent) == RED &&
    node_color(sibling(n)) == BLACK &&
    node_color(sibling(n)->left) == BLACK &&
    node_color(sibling(n)->right) == BLACK)
    {
    sibling(n)->color = RED;
    n->parent->color = BLACK;
    }
    else
    delete_case5(t, n);
    }

    void delete_case5(rbtree t, node n) {
    if (n == n->parent->left &&
    node_color(sibling(n)) == BLACK &&
    node_color(sibling(n)->left) == RED &&
    node_color(sibling(n)->right) == BLACK)
    {
    sibling(n)->color = RED;
    sibling(n)->left->color = BLACK;
    rotate_right(t, sibling(n));
    }
    else if (n == n->parent->right &&
    node_color(sibling(n)) == BLACK &&
    node_color(sibling(n)->right) == RED &&
    node_color(sibling(n)->left) == BLACK)
    {
    sibling(n)->color = RED;
    sibling(n)->right->color = BLACK;
    rotate_left(t, sibling(n));
    }
    delete_case6(t, n);
    }

    void delete_case6(rbtree t, node n) {
    sibling(n)->color = node_color(n->parent);
    n->parent->color = BLACK;
    if (n == n->parent->left) {
    assert (node_color(sibling(n)->right) == RED);
    sibling(n)->right->color = BLACK;
    rotate_left(t, n->parent);
    }
    else
    {
    assert (node_color(sibling(n)->left) == RED);
    sibling(n)->left->color = BLACK;
    rotate_right(t, n->parent);
    }
    }

    static node maximum_node(node n) {
    assert (n != NULL);
    while (n->right != NULL) {
    n = n->right;
    }
    return n;
    }

    void print_tree_helper(rbtree_node n, int indent) {
    int i;
    if (n == NULL) {
    fputs(“”, stdout);
    return;
    }
    if (n->right != NULL) {
    print_tree_helper(n->right, indent + INDENT_STEP);
    }
    for(i=0; icolor == BLACK)
    printf(“%d\n”, n->value);
    else
    printf(“\n”, n->value);
    if (n->left != NULL) {
    print_tree_helper(n->left, indent + INDENT_STEP);
    }
    }

    void print_tree(rbtree t) {
    print_tree_helper(t->root, 0);
    puts(“”);
    }

    int compare_int(int left, int right) {
    if (left right)
    return 1;
    else {
    assert (left == right);
    return 0;
    }
    }

    int main(){
    const int w = 3;
    int A[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = sizeof(A)/sizeof(A[0]);
    int i;
    rbtree r = rbtree_create();
    for(i=0; iroot)->value);
    for(i=w; iroot)->value);
    }
    return 0;
    }

    VN:F [1.9.22_1171]
    -1
  51. Hi got so many solutions on this page!…Wondering which ones are best???
    @1337c0d3r – Can you please comment about the best ones in the following manner:
    1. / /
    2. / /
    ….

    Thanks,
    Arnab.

    VA:F [1.9.22_1171]
    0
    • Hi got so many solutions on this page!…Wondering which ones are best???
      @1337c0d3r – Can you please comment about the best ones in the following manner:
      1. DStruct used? / Procedure used? / Complexity? / User? / Dated?
      2. — same format —
      ….

      Thanks,
      Arnab.

      VA:F [1.9.22_1171]
      0
  52. Hi got so many solutions on this page!…Wondering which ones are best???
    @1337c0d3r – Can you please comment about the best ones in the following manner:
    1. DStruct used? / Procedure used? / Complexity? / User? / Dated?
    2. — same format —
    ….

    Thanks,
    Arnab.

    VA:F [1.9.22_1171]
    0
    • The second method in original post is brilliant, it is O(n) by using a deque. Const time of fetching the max is trivial, const time removing is hard. Using a deque and following the rule of inserting (each insertion try to push the element to the leftmost as possible), this guarantees in each iteration, at most one element will be removed.

      VN:F [1.9.22_1171]
      0
  53. One of the best example of saving runtime complexity by choosing appropriate data structure.

    VN:F [1.9.22_1171]
    0
  54. Is it real O(n) by using deque?
    It is true insert + delete operations is 2n, but what about comparison before insert and delete? The number of comparison will change base on the size of deque (some time 1, some time w). If we pick the worst case – w, then, the algo’s running complexity will be O(nw), isn’t?

    VA:F [1.9.22_1171]
    0
  55. Actually we do not need the first while loop in the second for loop. See the following code in java.

    VA:F [1.9.22_1171]
    -1
  56. Really brilliant algorithm. Especially making the leap from O(1) stacks to this. Something to aspire to. For the slower among us, I did an annotated Java mockup complete with inductive proof in the comments.

    VA:F [1.9.22_1171]
    +1
    • Sorry, the board is eating my code. Let’s try the beginning of the for loop:

      VA:F [1.9.22_1171]
      0
  57. Try to post code again:


    import java.util.*;
    class MyClass {

    //wish I'd thought of this
    //but stolen from:
    //http://leetcode.com/2011/01/sliding-window-maximum.html
    public static void tweets_per_second(Integer[] tps, Integer k) {

    Deque dq = new LinkedList();

    for(int i = 0 ; i 0 && tps[i] >= tps[dq.peekLast()]) {
    dq.removeLast();
    }
    //critical point:
    //I don't add my value to the queue, rather I add my index in the source array
    //this will help determine when I'm no longer needed
    dq.addLast(i);

    //if your index is less than the start of the current window,
    //you get popped off the front of the queue (FIFO: oldest at the front)
    //You're too old.
    while(dq.size() > 0 && dq.peekFirst() <= (i - k)) {
    dq.removeFirst();
    }

    //pseudo proof:
    //we pull all the sub-optimals off the back
    //we pull all the geriatrics off the front
    // if there was something bigger that's not too old
    //it will be in front of me in the queue.
    //apply that reasoning inductively to every element
    //from the back of the queue moving to the front
    //therefore the max for the current window
    //should be sitting at the front of the queue.
    //print whatever is at the front of the queue

    System.out.println(tps[dq.peekFirst()]);

    }

    }

    }

    VA:F [1.9.22_1171]
    0
  58. The 2nd algorithm has complexity O(n log m), not as said O(n), assuming the sorted list is implemented by a heap.

    In the most inner loop, the complexity cost is not O(1). For the most inner loop, in the worst case, we need to remove 1 element and add 1 element to the sorted data structure. (The nature of the sliding window). The amortized cost is at least O(log m).

    In fact, complexity of any of Q.push_back(), Q.pop_back(), and Q.pop_front(), is not O(1).

    VA:F [1.9.22_1171]
    0
  59. Sorry, I was wrong. Please forget about my previous post. I understand it now. A more consolidate explanation about this problem: http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

    VA:F [1.9.22_1171]
    0
  60. So elegant code in o(n).
    For we just move forward by one step every time,so I consider we could use “if sentense” when remove the front elem in the queue.Here is the code:

    Besides,considering the case we move forward by more than one step,the “while sentense” is perfectly appropriate

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.