O(n) solution in Java with two simple pass in the array


  • 102
    Z

    For Example: A = [2,1,3,4,6,3,8,9,10,12,56], w=4

    1. partition the array in blocks of size w=4. The last block may have less then w.
      2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|

    2. Traverse the list from start to end and calculate max_so_far. Reset max after each block boundary (of w elements).
      left_max[] = 2, 2, 3, 4 | 6, 6, 8, 9 | 10, 12, 56

    3. Similarly calculate max in future by traversing from end to start.
      right_max[] = 4, 4, 4, 4 | 9, 9, 9, 9 | 56, 56, 56

    4. now, sliding max at each position i in current window, sliding-max(i) = max{right_max(i), left_max(i+w-1)}
      sliding_max = 4, 6, 6, 8, 9, 10, 12, 56

    code:

     public static int[] slidingWindowMax(final int[] in, final int w) {
        final int[] max_left = new int[in.length];
        final int[] max_right = new int[in.length];
    
        max_left[0] = in[0];
        max_right[in.length - 1] = in[in.length - 1];
    
        for (int i = 1; i < in.length; i++) {
            max_left[i] = (i % w == 0) ? in[i] : Math.max(max_left[i - 1], in[i]);
    
            final int j = in.length - i - 1;
            max_right[j] = (j % w == 0) ? in[j] : Math.max(max_right[j + 1], in[j]);
        }
    
        final int[] sliding_max = new int[in.length - w + 1];
        for (int i = 0, j = 0; i + w <= in.length; i++) {
            sliding_max[j++] = Math.max(max_right[i], max_left[i + w - 1]);
        }
    
        return sliding_max;
    }

  • 1
    Y

    How do you come up with "sliding-max(i) = max{rightmax(i), leftmax(i+w-1)}", it seems sliding-max(i) = max{leftmax(i), rightmax(i+w-1)} doesn't work. What's the difference here?


  • 0
    Z

    order of computing leftmax or right max doesn't matter... the direction of sliding window matter... if we slide from left to right than left_max should contain max we have seen past including current and right should contain max we will see in future (if we had slided the window). So, left or right may be vague term but concept is that left contains max from past window and right contains max from future window.


  • 0
    Z

    same logic is applicable if we need to compute sliding min from left to right.. the same code will work with only change of taking min instead of max


  • 0
    S

    elegant and wonderful solution, how did you come up with this idea? Everybody was using a queue and you thought out of box. great!


  • 0
    S

    elegant solution indeed!


  • 12
    W

    This is a nice solution. With some simple comparison, you can see this solution is somewhat equivalent to the deque solution.

    Because of the property of sliding window, you can find all these "anchor" points (advocated in OP's example), and then each sliding window can be divided into two parts. The idea is to find the maximum of the left part and the maximum of the right part, and then obtain the maxima by comparing the two maximums. The keen observation is that all the left maximums can be found by a right-to-left transverse, while all the right maximums can be found by a left-to-right transverse.

    Now think in the deque solution. When you add the new numbers into the deque from right, you will be comparing that number to the right-most number in the deque. If the new number is larger, then you pop out the right-most number and continue the comparison. This procedure is the same as the left-to-right transverse in OP's solution. Now let's say you continue the aforementioned procedure until you met the first number in the deque that is greater than the new number. You stop and push the new number into your deque. This procedure is similar to the right-to-left transverse in OP's solution.
    (The anchor points are determined automatically in deque, as you always pop out points that no longer belong to your sliding window.)

    In summary, all the "pop" action in deque solution corresponds to the "left-to-right" transverse in OP's solution and all the "push" action corresponds to the "right-to-left" transverse in OP's solution.


  • 4

    A very good method. But according to your explanation, I think you can use
    max_right[j] = ((j +1)% w == 0) ? in[j] : Math.max(max_right[j + 1], in[j]) instead of
    max_right[j] = (j % w == 0) ? in[j] : Math.max(max_right[j + 1], in[j]), although both of them can get the right answer.


  • 0
    T
    This post is deleted!

  • 0
    A

    Hey, would it be possible to explain this is more details.
    I mean I know it works, just that I am not able to understand how partitioning the array into blocks of size w and doing the left and right max things.


  • 2
    R

    Here is a short explanation to above algorithm.

    Suppose the numbers are | a , b , c ,d | e, f , g , h | ..
    After storing the max value for each window both in left and right direction, we have the arrays
    left : |a, b, b , d| e , e, e , h|..
    right: |d,d,d,d| h, h, h h | ..

    Finally in the last loop, when you're in the first window, the maxValue is calculated with following formula
    max(i) = Math.max( max_right[i], max_left[i+w-1] ) in this we test the maximum on both end of the window, i.e, left direction and right direction.
    and then we move to next window find their maximum.

    I hope it makes the algorithm clearer. Very nice idea and clean code.


  • 1
    Z

    @RT42 your are right on. good explanation.


  • 0
    A

    Though your logic is very clear, I had one doubt : Take the example :[3,2,1,4,5,6,2,3,4,5,7] k=4. In this example, I figured out the calculation manually as follows :

    left_max[] = 3,3,3,4 | 5,6,6,6 | 4,5,7
    right_max[]= 4,4,4,4|6,6,6,6|7,7,7
    

    According to this, the answer I got after manually working out the solution is [4,5,6,6,6,6,6,7] . However, the actual answer is [4,5,6,6,6,6,5,7].
    Could you please help me out to figure out where I am going wrong ?

    I also executed and debugged your code and got a different right_max[] array from the one you mentioned above.

    For the example : int[] arr = {2,1,3,4,6,3,8,9,10,12,56}, the right_max[] I get after iterating through all the numbers is :

    0_1479606956092_Problem+Max_SLiding.JPG

    Any help will be appreciated.N.B : The left[] max is same as you explained above.


  • 0
    G

    @aritra90tnp right_max should be

    4, 4, 4, 4 | 6, 6, 3, 3 | 7, 7, 7
    

  • 7
    D

    Here is the proof.

    Let's say the array is a0,a1,a2... an window width is w

    Our objective is to get the max array d[]. The array has length n-w+1
    We divide the entire array into windows from left edge and denote every element in the form of : i*w+j, i is the window index with offset 0 from left, j is the offset within the window. 0<=i<=n/w and 0<=j<w

    This is what we want to build:
    d[iw+j]=max(a[iw+j+x] where 0<=x<w) so iw+j actually represents the window from which we are calculating the max.

    Assuming we have the following arrays, (this is what dp is doing)
    left[iw+j] = left_max(a[iw+k] where 0<=k<j) Note the exclusive greater than.
    right[iw+j]= right_max(a[iw+k] where j<=k<=(i+1)*w-1)
    Array left[] is the accumulative max from left to right in each window
    Array right[] is the accumulative max from right to left in each window

    0_1487305176342_slidingWindow.jpg

    We have equation:
    d[iw+j]=max(right[iw+j], left[(i+1)w+j-1])
    d[iw+j]=max(right[iw+j], left[(iw+w+j-1])
    =>
    d[m] = max(right[m], left[m+w-1])

    The last element of d[] is d[n-w+1]=max(right[n-w+1], left[n-1])


  • 0
    O

    @derek3 what is iw?


  • 0
    D

    @owen.lin.75 I have edited my proof, sorry for the confusions.


  • 0
    S

    brilliant solution


  • 0
    Z

    @zahid2 As told by the problem setting "You can only see the k numbers in the window".Which means the data could be a stream in which case your algorithm might be not so applicable right? Just a question.
    Your solution is still brilliant.


  • 0
    C

    Very smart solution! Just some additional thought, I think the process may be tighter if we set the w = k - 1 instead of k.
    When you calculate the first number in your example 2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|, you actually calculate max(max(2), max(2, 1, 3, 4)).
    If you use 2, 1, 3 | 4, 6, 3 | 8, 9, 10 | 12, 56, you can use 2 only once by calculate max(max(4), max(2,1,3)). And the next one will be (4, 6), (1, 3).
    It’s really smart to partition the array into two parts. In other words, we need to ensure every slice with length k will be cut into exactly two parts by partition. If we set w < k – 1, array will be like 2, 1 | 3, 4 | 6, 3 | 8, 9 | 10, 12 | 56 |, then some case like max(max(1), max(3, 4), max(6)) will have 3 parts (similar to BST when w = 2).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.