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


  • 15

    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.

    Ruby

    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
        }
        out
    end
    

    Python

    def maxSlidingWindow(self, nums, k):
        d = collections.deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d += i,
            if d[0] == i - k:
                d.popleft()
            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.


  • 3

    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.


  • 4

    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
    S

    @StefanPochmann holy crap...


  • 0
    D

    @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
    C

    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
    L

    @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
    C

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


  • 0

    Hi dear Stefan, may I ask you a question: does faster means better, especially in practice or in an interview? A solution using deque for this question seems much wiser, but in practice, deque works slower and worst case would not be that worse. So in average cases, no deque solution could work better. Then, which one is the better solution?

    here's my code beats 99%

    public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length < 1) return new int[0];
            int n = nums.length - k + 1;
            int[] res = new int[n];
            int maxIndex = -1, maxValue = Integer.MIN_VALUE;
            
            for(int i = k - 1;i < nums.length;i++) {           
                if(maxIndex == -1) {
                    maxValue = Integer.MIN_VALUE;
                    for(int j = i;j > i - k;j--) {
                        if(nums[j] > maxValue) {
                            maxIndex = j;
                            maxValue = nums[j];
                        }
                    }
                }
                if(nums[i] >= maxValue) {
                    maxValue = nums[i];
                    maxIndex = i;
                }
                res[i - k + 1] = maxValue;
                if(maxIndex == i - k + 1) maxIndex = -1;
            }
            
            return res;
        }

Log in to reply
 

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