Deque based simple java solution that is clear to understand

  • 1

    So, this took me a while to understand, but i think that was mainly because some of the top rated answers were rather terse for my liking. I found this link very useful to visualize what's going on. Here's my (copied) version of the solution just annotated with some notes:

    	 * Maintain a dequeue that will allow you to delete from the beginning and the end easily.
    	 * Inside this deque, store indices of the array (not the elements themselves!). Here's the
    	 * invariant that needs to be maintained:
    	 * The "start" of the deque must have the index pointing to the biggest element in the current window.
    	 * This way, it's easy to add the top of the deque (via peek) to the result.
    	 * Any new element being considered should be compared to all elements in the deque. If it's larger,
    	 * then we delete everything from the tail and insert it.
    	 * @param nums
    	 * @param k
    	 * @return
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0) return nums;
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> queue = new ArrayDeque<>();
            for (int i = 0; i < nums.length; i++) {
            	int currIndex = i - k + 1;
    		if (currIndex >= 1) { // only once the currIndex is >= 1 should be consider trimming "old" indices
    	        	// Purge old indices if they exist in the queue
    			while (!queue.isEmpty() && queue.peekFirst() < currIndex) {
            	// keep the index pointing to the biggest element at the tail
            	while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
            	if (currIndex >= 0) {
            		res[currIndex] = nums[queue.peek()];
            return res;	

Log in to reply

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