Sliding Window Maximum

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.7/5 (109 votes cast)
Sliding Window Maximum, 4.7 out of 5 based on 109 ratings

94 thoughts on “Sliding Window Maximum

  1. Rya

    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]
    -2
    1. Krishnan

      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]
      +2
      1. Kaustubh

        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]
        +2
  2. 1337c0d3r

    @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
  3. Anonymous

    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]
    +3
  4. Anonymous

    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
    1. Soumitra Mishra

      (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
  5. 1337c0d3r

    @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]
    +1
  6. 1337c0d3r

    @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
  7. Anuj

    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
  8. Kay

    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
  9. bala

    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
    1. anonymous

      @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
  10. Vipul

    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]
    +1
    1. Profile photo of 1337c0d3r1337c0d3r Post author

      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
      1. codingC

        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]
        +1
  11. speeddy

    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
  12. anonymous

    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
    1. Profile photo of 1337c0d3r1337c0d3r Post author

      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
  13. Jason

    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
    1. Jason

      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
  14. Mikhail

    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
  15. Amit

    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
  16. Saurabh

    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
  17. Saurabh

    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
  18. Pingback: Multiplication of numbers | 口├人人│의 Blog

  19. lipingwu

    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
  20. sachin

    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
  21. Shaobi Li

    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
    1. jijex

      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
  22. japanbest

    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
  23. Profile photo of sivsiv

    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
  24. shushant arora

    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
  25. shushant arora

    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
  26. veeru

    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
  27. kanika sharma

    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
  28. jiaji

    //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
  29. Chun

    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
  30. sreenivasan

    @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
  31. zyfo2

    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
    1. xsong

      See my second post.

      Simpliest, we still have a sorted buffer with w elements. Each time a new input comes, remove the one with lowest index and insert sorting (binary) to update the buffer, and output the max — the first value in the buffer.

      The two drawback, 1. insert cost, 2. search lowest index, can be overcomed in my solution.

      VA:F [1.9.22_1171]
      0
  32. amit mall

    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
  33. Profile photo of frankfrank

    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
  34. Profile photo of frankfrank

    here is the code using the red black tree. Apprently the time complexity is O(nlog(m)).

    VN:F [1.9.22_1171]
    -1
  35. Profile photo of frankfrank

    #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
  36. Arnab Dutta

    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
    1. Arnab Dutta

      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
  37. Arnab Dutta

    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
    1. Profile photo of JQueueJQueue

      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
  38. Pingback: max num in the sliding window | kiddy

  39. jijex

    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
  40. hakki

    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
  41. rob h

    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
    1. rob h

      Sorry, the board is eating my code. Let’s try the beginning of the for loop:

      VA:F [1.9.22_1171]
      0
  42. rob h

    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
  43. Robin Hsu

    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
  44. losato

    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
  45. Profile photo of rpzwrpzw

    I’m not so sure it’s O(n). Yes there are at most 2n insert/delete, but for each insert it’s worse case w comparisons. If the array is sorted in descending order, wouldn’t it take w*n comparisons?

    But I’m almost dozing off at work. So please correct me.

    VN:F [1.9.22_1171]
    0
  46. xsong

    I think for the filter application with dynamic input and a sliding window operation basic a given static data have some difference. However, following algorithm should be able to modified to fit both.

    For a given set of data, 1xn array
    0. set output array (n-w+1 elements, or we can padding the input array to make the output same dimension — this is normally the case for filter) to min value possible (minimal integer, or zero for unsigned)
    1. quick sort based on given library, which should take O(nlogn), the sorted array need only the index
    2. loop in the sorted array, from max to min (we can also skip the last w-1 for this special case), we set [index – w + 1, index + w -1] in the output array to the value, if and only if
    2.a the index is not out of range of output array.
    2.b the output array element has the initial minimal value preset.

    The concept can be derived from following operation:
    Plot the array in excel
    From the max to min, draw a flat line with width 2w-1, till there is already a line above.
    The minimal w-1 data has no chance to pop out

    Demonstrate it with the data in example:
    #define minv = 0x10000000
    Input[] = {1, 3, -1, -3, 5, 3, 6, 7};
    windw = 3;
    SortedV[] = {7, 6, 5, 3, 3, 1, -1, -3};
    SortedIndex[] = {8, 7, 5, 2, 6, 1, 3, 4};
    /*initial output, for this problem it is 8 – 3 + 1 elements */
    Output[] = {minv , minv , minv , minv , minv , minv , minv };
    /*First loop, index 8, start from 8 – 3 + 1 to 8 + 3 – 1, i.e. output index [6,10], set to 7 if the element still has the initial value and the index is in range*/
    /*Output[] = {minv , minv , minv , minv , minv , minv , 7 };*/

    /*2nd loop, index 7, start from 7 – 3 + 1 to 7 + 3 – 1, i.e. output index [5,10], set to 6 if the element still has the initial value and the index is in range*/
    /*Output[] = {minv , minv , minv , minv , minv ,6 , 7 };*/

    /*3rd loop, index 5, start from 5 – 3 + 1 to 5 + 3 – 1, i.e. output index [3,7], set to 5 if the element still has the initial value and the index is in range*/
    /*Output[] = {minv, minv, minv, 5, 5, 6 , 7 };*/

    /*4th loop, index 2, start from 2 – 3 + 1 to 2 + 3 – 1, i.e. output index [0,4], set to 3 if the element still has the initial value and the index is in range*/
    /*Output[] = {3, 3, 3, 5, 5, 6, 7 };*/

    /*5th loop, index 6, start from 6 – 3 + 1 to 6 + 3 – 1, i.e. output index [4,8], set to 3 if the element still has the initial value and the index is in range*/
    /*Output[] = {3, 3, 3, 5, 5, 6, 7 };*/

    /*6th loop, index 1, start from 1 – 3 + 1 to 1 + 3 – 1, i.e. output index [-1,3], set to 3 if the element still has the initial value and the index is in range*/
    /*Output[] = {3, 3, 3, 5, 5, 6, 7 };*/

    End loop

    When the data is input one by one to the function like the digital filter, we can consider a fixed w sorted array, updated by insert sorting, however, when the w is not big, the additional cost of insertion and deleting will compromise the result

    VA:F [1.9.22_1171]
    0
    1. xsong

      Need to clean up the extra code
      Q.push(Pair(A[i], i));
      for (int i = w; i < n; i++) {
      Pair p = Q.top();
      B[i-w] = p.first;
      while (p.second <= i-w) {
      Q.pop();
      p = Q.top();
      }
      Q.push(Pair(A[i], i));
      }
      B[n-w] = Q.top().first;

      VA:F [1.9.22_1171]
      0
  47. xsong

    1337c0d3r’s first implementation, which in my opinion a more general case for the running time filter which accept one value and output a value each time, can be further improved.

    Suppose window size 5, and the sorted array (or priority queue in the implementation), hold following pairs

    Values: 9 8 5 4 2
    Index: 3 5 2 1 4

    Now feed another value to the filter, say 7 with index 6. First a modified binary search (do not insert) can determine the location it should be:

    Values 9 8 [7] 5 4 2
    Index 3 5 [6] 2 1 4

    At this point, we don’t care 5 4 2 any more, because they never have a chance to be a the max in the window. Based on the observation, we can:
    First, overwrite the element ([5, 2] pair) to become:
    Values 9 8 7 4 2
    Index 3 5 6 1 4
    Then we decrease the element count in the array to 3, so that the array only has
    Values 9 8 7
    Index 3 5 6

    For the case has same value, we always put it to the end.
    Now we have the first benefit, the binary search is not always among w elements. However, it is somewhat trivial. Another benefit, at least we avoid some memory move.

    A further observation is, if the above rule apply from very beginning, the array always:
    a. the values decreases
    b. the index increases

    Now, we only need to throw the first pair, if it moves out of window, instead of check among w.
    In filter application with round buffer, the above can avoid memory move totally. We need just one index for the start point, one integer to record total.

    We only need to check the first element to determine if need to be discarded.
    If it should be discarded, increase the start index by 1, and decrease length by 1.
    Then we binary search to determine where the new value should be inserted, we simply replace that cell, then change the sorted array length, no memory move involved.

    VA:F [1.9.22_1171]
    0
    1. xsong

      Correction:
      1. line 48:
      pFilter->buffer[i].index = iii ++;

      2. The comment for the modifiedBinarySearch, if there are same values, it does not matter where to insert it. So we can simplified the search by discard the further search for the first value less than the feed.
      Strictly, if we need a logic for it, put the new feed as the first of all the same values and discard all the elements after it would decrease the search attempt more.

      VA:F [1.9.22_1171]
      0
  48. jy

    Here’s a DP solution in O(n) time and O(n) space.

    First, divide the input array into N/w non-overlapping windows. For the example given in the problem, here are the 3 windows:

    [1 3 -1] [-3 5 3] [6 7]

    Trivially, it takes O(N) time to compute max value for each of the N/w windows.

    But that doesn’t solve the problem. We need the max numbers for the *overlapping* windows.

    What to do when we compute the max for window [5, 3, 6] for example?

    It turns out, the following property holds:

    max of [5, 3, 6] = max(
    max of [5, 3] from previous window [-3, 5, 3],
    max of [6] from current window [6, 7]
    );

    For any given overlapping window, we can break it into two parts, the left part is a right-aligned sub-range of the previous window; the second part is a left-aligned sub-range of the next window.

    If we had kept all the right-aligned max numbers and left-aligned max numbers for each of the N/w windows, the problem is solved by taking the max of the above two sub-ranges.

    Since there are N/w non-overlapping windows, and each needs to keep w left-aligned max numbers and w right-aligned max numbers, the total time is N / w * w * 2 = 2N.

    Computing w left-aligned max numbers is O(w):

    left[0] = input[windowStart];
    for (int i = 1; i < w; i++) {
    left[i] = max(left[i – 1], input[windowStart + i]);
    }

    The same for the right-aligned max numbers.

    VA:F [1.9.22_1171]
    0
  49. Pingback: Sliding Window Max | moonstonelin

  50. Profile photo of wqedwqdswqswqwqedwqdswqswq

    Correction:
    1. line 48:
    pFilter->buffer[i].index = iii ++;

    2. The comment for the modifiedBinarySearch, if there are same values, it does not matter where to insert it. So we can simplified the search by discard the further search for the first value less than the feed.
    Strictly, if we need a logic for it, put the new feed as the first of all the same values and discard all the elements after it would decrease the search attempt more. timberland Homme

    VN: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.