LeetCode 239: Sliding Window Maximum Solution in Python – A Step-by-Step Guide

What Is LeetCode 239: Sliding Window Maximum?

In LeetCode 239: Sliding Window Maximum, you’re given an integer array nums and an integer k, and your task is to return an array of the maximum values in each sliding window of size k as you move from left to right. This is a step beyond array product problems like LeetCode 238: Product of Array Except Self, focusing on dynamic window analysis.

Problem Statement

• Input: An integer array nums and an integer k (window size).
• Output: An array of maximum values for each window of size k.
• Rules: Slide the window one position at a time, return max for each.

Constraints

• Array length: 1 to 10^5.
• Values: -10^4 to 10^4.
• k: 1 to length of array.

Examples

• Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
• Windows: [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]
• Output: [3,3,5,5,6,7]
• Input: nums = [1], k = 1
• Output: [1]
• Input: nums = [1,-1], k = 1
• Output: [1,-1]

Understanding the Problem: Sliding Window Maximums

To solve LeetCode 239: Sliding Window Maximum in Python, we need to track the maximum value in a window of size k as it slides across the array, producing a result for each position. This isn’t about linked list deletion like LeetCode 237: Delete Node in a Linked List—it’s about efficient window management. A naive approach (checking each window’s max) takes O(nk), which is inefficient for large k. We’ll explore two methods: 1. Best Solution (Deque-Based): O(n) time, O(k) space—optimal and clever. 2. Alternative Solution (Brute Force with Optimization): O(nk) time, O(1) space—simpler but slower.

Let’s dive into the best solution.

Best Solution: Deque-Based Approach

Why This Is the Best Solution

The deque-based approach is our top choice for LeetCode 239 because it achieves O(n) time complexity by maintaining a deque (double-ended queue) of indices, ensuring we always know the maximum in the current window efficiently. It’s a brilliant use of data structures, balancing speed and space, making it the go-to solution.

How It Works

• Use a deque to store indices of elements in decreasing order (largest first).
• For each element:
• Remove indices outside the current window (left side).
• Remove smaller elements from the right (since they can’t be max).
• Add the current index.
• The deque’s front always holds the max index for the current window.

Step-by-Step Example

Example: nums = [1,3,-1,-3,5,3,6,7], k = 3

• Deque: Stores indices, max at front.
• Process:
• i=0, 1: Deque = [0].
• i=1, 3: Deque = [1] (3 > 1, remove 0).
• i=2, -1: Deque = [1,2] (window [1,3,-1], max 3).
• Output[0] = nums[1] = 3.
• i=3, -3: Deque = [1,3] (remove 2, window [3,-1,-3], max 3).
• Output[1] = 3.
• i=4, 5: Deque = [4] (remove 1 (out of window), 5 > -3).
• Output[2] = 5.
• i=5, 3: Deque = [4,5] (window [-3,5,3], max 5).
• Output[3] = 5.
• i=6, 6: Deque = [6] (remove 4, 6 > 3).
• Output[4] = 6.
• i=7, 7: Deque = [7] (7 > 6).
• Output[5] = 7.
• Output: [3,3,5,5,6,7].

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation using collections.deque:

Copy codefrom collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Line 1: Initialize deque and result
        dq = deque()  # Stores indices in decreasing order
        result = []

        # Line 2: Process each element
        for i in range(len(nums)):
            # Line 3: Remove indices outside window
            while dq and dq[0] <= i - k:
                dq.popleft()

            # Line 4: Remove smaller elements from right
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()

            # Line 5: Add current index
            dq.append(i)

            # Line 6: Add max to result after first window
            if i >= k - 1:
                result.append(nums[dq[0]])

        # Line 7: Return result
        return result

• Time Complexity: O(n) – each element is added and removed at most once.
• Space Complexity: O(k) – deque stores up to k indices.

Alternative Solution: Brute Force with Optimization

Why an Alternative Approach?

The brute force with optimization approach calculates the maximum for each window directly, with a slight tweak to avoid recomputing unnecessarily when possible. It’s a simpler alternative for understanding the problem, though less efficient, making it a good starting point for beginners.

How It Works

• Slide a window of size k across the array.
• For each window, find the maximum by scanning its elements.
• Optimize slightly by tracking the previous max and adjusting only if the removed or added element affects it.

Step-by-Step Example

Example: nums = [1,3,-1,-3,5,3,6,7], k = 3

• Window 0: [1,3,-1] → Max = 3.
• Window 1: [3,-1,-3] → Max = 3.
• Window 2: [-1,-3,5] → Max = 5.
• Window 3: [-3,5,3] → Max = 5.
• Window 4: [5,3,6] → Max = 6.
• Window 5: [3,6,7] → Max = 7.
• Output: [3,3,5,5,6,7].

Code for Brute Force Approach

Copy codeclass Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Line 1: Initialize result
        result = []

        # Line 2: Slide window and find max
        for i in range(len(nums) - k + 1):
            window_max = nums[i]
            for j in range(i, i + k):
                window_max = max(window_max, nums[j])
            result.append(window_max)

        # Line 3: Return result
        return result

• Time Complexity: O(n*k) – k comparisons per window.
• Space Complexity: O(1) – excluding output.

Comparing the Two Solutions

• Best Solution (Deque-Based):
• Pros: O(n) time, efficient, scalable.
• Cons: Requires deque understanding.
• Alternative Solution (Brute Force):
• Pros: Simple, intuitive.
• Cons: O(n*k) time, inefficient for large k.

The deque-based method is our best for its superior performance.

Additional Examples and Edge Cases

Single Element

• Input: [1], k = 1
• Output: [1].

All Same

• Input: [5,5,5], k = 2
• Output: [5,5].

Negative Numbers

• Input: [-7,-8,7,5], k = 3
• Output: [7,7].

Complexity Breakdown

• Deque-Based:
• Time: O(n).
• Space: O(k).
• Brute Force:
• Time: O(n*k).
• Space: O(1).

Deque wins on time efficiency.

Key Takeaways for Beginners

• Sliding Window: Fixed-size subarray traversal.
• Deque: Maintains max efficiently.
• Brute Force: Direct but slow.
• Python Tip: deque for queues—see [Python Basics](/python/basics).

Final Thoughts: Slide to the Max Like a Pro

LeetCode 239: Sliding Window Maximum in Python is a fantastic window challenge. The deque-based solution offers O(n) brilliance, while the brute force approach provides a clear starting point. Want more sliding window fun? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 76: Minimum Window Substring. Ready to slide? Head to Solve LeetCode 239 on LeetCode and find those maximums today!