LeetCode 239: Sliding Window Maximum Solution

Master LeetCode problem 239 (Sliding Window Maximum), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

239. Sliding Window Maximum

Hard

Array Queue Sliding Window Heap (Priority Queue)Monotonic Queue

Problem Explanation

Explanation:

To solve this problem, we can use a deque (double-ended queue) to store the indices of the elements in the current window. We maintain the deque in such a way that the front of the deque always contains the index of the maximum element in the current window.

At each step, we do the following:

Remove indices from the front of the deque that are outside the current window.
Remove indices from the back of the deque that correspond to elements smaller than the current element.
Add the index of the current element to the back of the deque.

The front of the deque will always contain the index of the maximum element in the current window. We add this maximum element to the result whenever the window size reaches k.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of elements in the input array.

Space Complexity:

The space complexity is O(n) as we are using a deque to store indices.

Solution Code

import java.util.*;

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 239 (Sliding Window Maximum)?

This page provides optimized solutions for LeetCode problem 239 (Sliding Window Maximum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 239 (Sliding Window Maximum)?

The time complexity for LeetCode 239 (Sliding Window Maximum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 239 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 239 in Java, C++, or Python.

Back to LeetCode Solutions