Java O(n) solution using deque with explanation


  • 210
    F

    We scan the array from 0 to n-1, keep "promising" elements in the deque. The algorithm is amortized O(n) as each element is put and polled once.

    At each i, we keep "promising" elements, which are potentially max number in window [i-(k-1),i] or any subsequent window. This means

    1. If an element in the deque and it is out of i-(k-1), we discard them. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array

    2. Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] <a[i] and x<i, then a[x] has no chance to be the "max" in [i-(k-1),i], or any other subsequent window: a[i] would always be a better candidate.

    3. As a result elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]


    public int[] maxSlidingWindow(int[] a, int k) {		
    		if (a == null || k <= 0) {
    			return new int[0];
    		}
    		int n = a.length;
    		int[] r = new int[n-k+1];
    		int ri = 0;
    		// store index
    		Deque<Integer> q = new ArrayDeque<>();
    		for (int i = 0; i < a.length; i++) {
    			// remove numbers out of range k
    			while (!q.isEmpty() && q.peek() < i - k + 1) {
    				q.poll();
    			}
    			// remove smaller numbers in k range as they are useless
    			while (!q.isEmpty() && a[q.peekLast()] < a[i]) {
    				q.pollLast();
    			}
    			// q contains index... r contains content
    			q.offer(i);
    			if (i >= k - 1) {
    				r[ri++] = a[q.peek()];
    			}
    		}
    		return r;
    	}

  • 18

    Clever idea to keep the indexes in that way. I just rewrite your code in C++ :-) Thanks for your sharing.

    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> windowMax;
            deque<int> dq;
            for (int i = 0; i < n; i++) {
                while (!dq.empty() && dq.front() < i - k + 1)
                    dq.pop_front();
                while (!dq.empty() && nums[dq.back()] < nums[i])
                    dq.pop_back();  
                dq.push_back(i);
                if (i >= k - 1) windowMax.push_back(nums[dq.front()]);
            }
            return windowMax;
        }
    };

  • 12
    Q

    Thanks for your sharing! Actually first while in the for loop can be replace by if, since it only needs to be executed once.


  • 0
    P

    for the input [] 0, your code return null, but the expected is []


  • 3
    S

    python version:

    from collections import deque
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            if not nums: return []
            res = []
            dq = deque()  # store index
            for i in xrange(len(nums)):
                if dq and dq[0]<i-k+1:  # out of the window
                    dq.popleft()
                while dq and nums[dq[-1]]<nums[i]:  # remove impossible candidate
                    dq.pop()
                dq.append(i)
                if i>k-2:
                    res.append(nums[dq[0]])
            return res

  • 0
    F

    Thanks that's corrected


  • -1
    A
    This post is deleted!

  • 0
    T

    LinkedList implements Deque interface too, so you could have just changed one word in OP's code to achieve this...

    Also that main while loop is clearly a for loop with all parts (init, cond, incr) scattered around.


  • -1
    J

    I would say that the complexity of this solution is O(kn - k^2). In the worst case when the original array is decreasing, the given solution has to check every number in a sliding window, and the complexity is O(k). Since there are n-k windows in total, the total complexity is O(k*(n-k)) =O(kn - k^2). I believe this is different from a standard O(n).


  • 0
    W
    This post is deleted!

  • 30
    E

    Very nice and intuitive solution! Thanks for sharing!

    However, the first while loop is unnecessary since we only pop out one out of range element in one round at most. (one round we only accept one element, so we pop at most one element out).

    Here is an AC solution with "if"

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            if (n == 0) {
                return nums;
            }
            int[] result = new int[n - k + 1];
            LinkedList<Integer> dq = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                if (!dq.isEmpty() && dq.peek() < i - k + 1) {
                    dq.poll();
                }
                while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                    dq.pollLast();
                }
                dq.offer(i);
                if (i - k + 1 >= 0) {
                    result[i - k + 1] = nums[dq.peek()];
                }
            }
            return result;
        }
    }
    

  • 4
    J

    So when the array is in descending order, the queue size will be k. However, you will never get into the second inner loop while (!q.isEmpty() && a[q.peekLast()] < a[i]), because the last element already does NOT satisfy the condition. In other words, all inner loop is actually in constant time. So total still O(n).


  • 0
    J

    Yes, I agree with you.


  • 0
    O

    Genius solution


  • 0
    R

    It seems you haven't considered the case where k > a.length


  • 3
    H

    Why are you storing element index instead of storing element value?
    This is my solution storing element value, but got null pointer exception on the longest test case. I'd appreciate it if someone could help me figure out the problem!

    public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length == 0){
                return new int[0];
            }
            int n = nums.length;
            Deque<Integer> q = new ArrayDeque<Integer>();
            int[] res = new int[nums.length - k + 1];
            List<Integer> list = new ArrayList<Integer>();
            int t = 0;
            for(int i = 0; i < nums.length; i++){
            	while(!q.isEmpty() && q.peekLast() < nums[i]){
            		q.poll();
            	}
            	q.addLast(nums[i]);
            	if(i > k - 1 && q.peekFirst() == nums[i - k]){
            		q.pollFirst();
            	}
            	if(i >= k - 1){
            		res[t++] = q.peekFirst();
            	}	
            }
            return res;
        }

  • 0
    P
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            # maitain a decreasing queue
            que, result = collections.deque(), []
            for i, n in enumerate(nums):
                # remove all smaller predecessors
                while que and que[-1][0] <= n:
                    que.pop()
                que.append((n, i))
                if i >= k - 1:
                    # remove all out of range max values
                    while que[0][1] + k <= i:
                        que.popleft()
                    result.append(que[0][0])
            return result
    

    Thanks for sharing!


  • 0
    L

    @han38 hey I have the same question. when i<k, lets say i=1&& k=3, nums[i-k]'s index is out of bounds ....


  • 0
    L

    @han38 Hi, could you please give me a short hint why or how you get this if condition.... Appreciate it!
    if(i > k - 1 && q.peekFirst() == nums[i - k]){
    q.pollFirst();
    }


  • 1
    P

    @han38 There was a very tiny small problem with your code :
    q.poll() removes from the front of the queue. You should Use pollLast() instead.
    Apart from that your code is absolutely good to go !

    here is your version of the code :

    public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length == 0){
                return new int[0];
            }
            int n = nums.length;
            Deque<Integer> q = new ArrayDeque<Integer>();
            int[] res = new int[nums.length - k + 1];
            List<Integer> list = new ArrayList<Integer>();
            int t = 0;
            for(int i = 0; i < nums.length; i++){
            	while(!q.isEmpty() && q.peekLast() < nums[i]){
            		q.pollLast(); // The only change which I did !
            	}
            	q.addLast(nums[i]);
            	if(i > k - 1 && q.peekFirst() == nums[i - k]){
            		q.pollFirst();
            	}
            	if(i >= k - 1){
            		res[t++] = q.peekFirst();
            	}	
            }
            return res;
        }
    

Log in to reply
 

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