9 lines Ruby, 11 lines Python, O(n)

  • 22

    Keep indexes of good candidates in deque d. The indexes in d are from the current window, they're increasing, and their corresponding nums are decreasing. Then the first deque element is the index of the largest window value.

    For each index i:

    1. Pop (from the end) indexes of smaller elements (they'll be useless).
    2. Append the current index.
    3. Pop (from the front) the index i - k, if it's still in the deque (it falls out of the window).
    4. If our window has reached size k, append the current window maximum to the output.


    Apparently Ruby doesn't have a deque, so I simulate one with an array, where s tells the start index of the queue in the array.

    def max_sliding_window(nums, k)
        d, s = [], 0
        out = []
        nums.each_index{ |i|
            d.pop while d[s] && nums[d[-1]] < nums[i]
            d << i
            s += 1 if d[s] == i - k
            out << nums[d[s]] if i >= k - 1


    def maxSlidingWindow(self, nums, k):
        d = collections.deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
            d += i,
            if d[0] == i - k:
            if i >= k - 1:
                out += nums[d[0]],
        return out

    Last three lines could be this, but for relatively large k it would waste space:

            out += nums[d[0]],
        return out[k-1:]

  • 0

    Two golfing languages? Just finish reading the wikipedia page on code golfing :-) Well, Python is much more readble to me.

  • 5

    Nah, that's not really golfing. This is:

    def max_sliding_window(n,k)d,s=[],0;o=[];n.each_index{|i|d.pop while
    d[s]&&n[d[-1]]<n[i];d<<i;s+=1if d[s]==i-k;o<<n[d[s]]if i>k-2};o end

    Besides getting rid of unnecessary space and making variables only one letter long, note for example the 1if without a space in between, or that I changed i >= k - 1 to i>k-2.

  • 6

    Shaved off three more bytes:

    def max_sliding_window(n,k)d,s=[],0;o=[];n.each_index{|i|d.pop while
    d[s]&&n[d[-1]]<n[i];d<<i;d[s]>i-k||s+=1;i>k-2&&o<<n[d[s]]};o end

  • 1

    Stefan, you're the ultimate golfer!

  • 0

    @StefanPochmann holy crap...

  • 0

    @StefanPochmann sorry, but why does your code has 'commas' at the end of lines? I see two instances.

    ---> I realize that += followed by , is actually equivalent to 'append' for a list. :) I didn't know this!

  • 0

    I have a question about why the run time is O(n)? Consider the following sequence nums = [2,1,0,9,2,1,0,9,2,1,0,9.....], which is a periodic sequence with period 4. Then let the window size be k=3. So in the first window, the dqueue is d=[2,1,0], then when the new entry 9 comes, it will have to compare with all of these 3 numbers, which result in k operations. Then the maximum 9 will stay there for 3 steps, until the window includes 2,1,0 again, then the next time the 9 comes again, it again requires k operations. So it's O(n*k/p) right? n is length of nums, k is window size and p is period

  • 0

    @chenjin2011 Your n*k/p is less than n, so I'm not sure what your point is. Do you mean my solution is better than O(n) or do you mean it is worse than O(n)?

  • 0

    @StefanPochmann You could save some space if you do while d and nums[d[-1]]<=n instead of < in the case of a list of many duplicates. However, you would be trading off time potentially.

  • 0

    I figure it out. Never mind, it is O(n)

  • -1
    This post is deleted!

  • 0

    @JayS03 It might be faster in certain cases but the interviewer will ask you to optimize the code to O(n). Otherwise, a O(nk) solution is meaningless because it's trivial nested for loop and everyone can finish that in 5-10 mins.

    Besides, how do you get this conclusion that non-deque solution is faster than deque solution in average? Just because your code beats 99% on OJ? Your code running fast on Leetcode OJ doesn't mean your algorithm will faster than others. Only 18 cases are tested in this problem. When K is larger, this O(nk) will sure slower than Deque solution.

Log in to reply

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