LeetCode 480: Sliding Window Median Solution in Python – A Step-by-Step Guide

What Is LeetCode 480: Sliding Window Median?

In LeetCode 480: Sliding Window Median, you’re given an array of integers nums and an integer k, representing the size of a sliding window. Your task is to find the median of each contiguous window of size k as it slides from left to right, returning an array of these medians. The median is the middle value (for odd k) or average of two middle values (for even k). For example, with nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the medians are [1, -1, -3, 3, 5, 6, 7]. It’s like watching a number parade through a fixed-size spotlight, noting the center value each time.

Problem Statement

• Input: nums (List[int])—array of integers; k (int)—window size.
• Output: List[float]—medians of each sliding window.
• Rules:
• Window slides one position at a time.
• Median: middle value (odd k) or average of two middle values (even k).
• Return exact floating-point values.

Constraints

• 1 <= k <= nums.length <= 10^5.
• -2^31 <= nums[i] <= 2^31 - 1.

Examples to Get Us Started

• Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
• Output: [1.0,-1.0,-1.0,3.0,5.0,6.0,7.0] (Windows: [1,3,-1] → 1, [3,-1,-3] → -1, etc.).
• Input: nums = [1,2,3,4], k = 2
• Output: [1.5,2.5,3.5] (Windows: [1,2] → 1.5, [2,3] → 2.5, [3,4] → 3.5).
• Input: nums = [1], k = 1
• Output: [1.0].

Understanding the Problem: Tracking the Middle

To solve LeetCode 480: Sliding Window Median in Python, we need to compute the median of each window of size k as it slides across nums, handling both odd and even k efficiently. A naive approach—sorting each window—could be O(n * k log k), slow for n = 10^5 and k = 10^5. The key? Use two heaps to maintain a balanced set of numbers, allowing O(log k) updates per slide. We’ll explore:

• Best Solution (Two Heaps with Balanced Maintenance): O(n log k) time, O(k) space—fast and optimal.
• Alternative Solution (Brute Force Sorting): O(n * k log k) time, O(k) space—simple but inefficient.

Let’s dive into the two-heaps solution—it’s the tracker’s dynamic spotlight we need.

Best Solution: Two Heaps with Balanced Maintenance

Why This Is the Best Solution

The two-heaps approach is the top pick because it’s O(n log k) time and O(k) space, efficiently maintaining the median by using a max heap for the smaller half and a min heap for the larger half of the window, balancing them as the window slides. It updates in O(log k) per element addition/removal, avoiding full sorts. It’s like keeping two balanced piles of numbers, always ready to spotlight the middle—clever and swift!

How It Works

Here’s the strategy:

• Step 1: Use two heaps:
• small (max heap): smaller half (or equal size for even k).
• large (min heap): larger half.
• Step 2: Initialize first window:
• Add k elements, balance heaps (small ≤ large size ≤ small + 1).
• Step 3: Slide window:
• Remove outgoing element, add incoming element.
• Rebalance heaps.
• Compute median: top of small (odd k) or avg of tops (even k).
• Step 4: Collect medians in result array.
• Why It Works:
• Heaps keep median at boundary in O(log k) per update.
• Balance ensures constant-time median access.

Step-by-Step Example

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

• Init Window [1,3,-1]:
• Small: [1], Large: [-1, 3].
• Rebalance: Small: [-1], Large: [1, 3], median = 1.
• Slide to [3,-1,-3]:
• Remove 1 (Large), add -3 (Small).
• Small: [-3, -1], Large: [3], rebalance: Small: [-3], Large: [-1, 3], median = -1.
• Slide to [-1,-3,5]:
• Remove 3 (Large), add 5 (Large).
• Small: [-3], Large: [-1, 5], median = -1.
• Continue: Medians = [1, -1, -1, 3, 5, 6, 7].
• Result: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0, 7.0].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codefrom heapq import heappush, heappop, heapify

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        # Step 1: Initialize heaps
        small = []  # Max heap (negated for min heap simulation)
        large = []  # Min heap
        result = []

        # Step 2: Process first window
        for i in range(k):
            heappush(small, -nums[i])
        for _ in range(k // 2):
            heappush(large, -heappop(small))

        # Step 3: Slide window
        for i in range(k, len(nums)):
            # Compute median for current window
            if k % 2 == 0:
                median = (-small[0] + large[0]) / 2.0
            else:
                median = float(-small[0])
            result.append(median)

            # Remove outgoing element
            out = nums[i - k]
            if out <= -small[0]:
                small.remove(-out)
                heapify(small)
            else:
                large.remove(out)
                heapify(large)

            # Add incoming element
            incoming = nums[i]
            if small and incoming <= -small[0]:
                heappush(small, -incoming)
            else:
                heappush(large, incoming)

            # Rebalance heaps
            while len(small) > len(large) + 1:
                heappush(large, -heappop(small))
            while len(large) > len(small):
                heappush(small, -heappop(large))

        # Last window
        if k % 2 == 0:
            result.append((-small[0] + large[0]) / 2.0)
        else:
            result.append(float(-small[0]))

        return result

• Line 6-9: Init heaps and result.
• Line 12-15: Fill first window, balance (small ≤ large ≤ small + 1).
• Line 18-38: Slide:
• Compute median (avg for even k, small top for odd).
• Remove outgoing (adjust heap), add incoming.
• Rebalance heaps.
• Line 41-44: Compute last window’s median.
• Time Complexity: O(n log k)—n slides, O(log k) heap ops.
• Space Complexity: O(k)—heap sizes.

It’s like a median-tracking maestro!

Alternative Solution: Brute Force Sorting

Why an Alternative Approach?

The brute force sorting method—O(n * k log k) time, O(k) space—sorts each window to find the median directly, recomputing for every slide. It’s slow but intuitive, like sorting a handful of numbers each time the spotlight moves. Good for small n or learning!

How It Works

• Step 1: For each window i to i+k-1:
• Extract subarray.
• Sort it.
• Compute median (middle or avg of two middles).
• Step 2: Collect medians in result.
• Step 3: Return result array.

Step-by-Step Example

Example: nums = [1,3,-1], k = 3

• Window [1,3,-1]:
• Sort: [-1,1,3], median = 1.
• Result: [1.0].

Code for Brute Force

Copy codeclass Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        result = []
        for i in range(len(nums) - k + 1):
            # Step 1: Extract and sort window
            window = sorted(nums[i:i + k])
            # Compute median
            if k % 2 == 0:
                median = (window[k // 2 - 1] + window[k // 2]) / 2.0
            else:
                median = float(window[k // 2])
            result.append(median)
        return result

• Line 4-11: Sort each window, compute median, append.
• Time Complexity: O(n * k log k)—n windows, k log k sort.
• Space Complexity: O(k)—window array.

It’s a slow spotlight sorter!

Comparing the Two Solutions

• Two Heaps (Best):
• Pros: O(n log k), fast, scalable.
• Cons: O(k) space, heap complexity.
• Brute Force (Alternative):
• Pros: O(n * k log k), simple.
• Cons: Slow for large n, k.

Two heaps win for efficiency.

Edge Cases and Examples

• Input: [1], k=1 → [1.0].
• Input: [1,1], k=2 → [1.0].
• Input: [2147483647,-2147483648], k=2 → [0.5].

Two heaps handle all well.

Complexity Recap

• Two Heaps: Time O(n log k), Space O(k).
• Brute Force: Time O(n * k log k), Space O(k).

Two heaps are the champ.

Key Takeaways

• Two Heaps: Balance for speed.
• Brute Force: Sort each time.
• Python Tip: Heaps optimize—see [Python Basics](/python/basics).

Final Thoughts: Track That Median

LeetCode 480: Sliding Window Median in Python is a dynamic data-tracking adventure. Two heaps are your fast spotlight, while brute force is a slow sorter. Want more sliding fun? Try LeetCode 295: Find Median from Data Stream or LeetCode 239: Sliding Window Maximum. Ready to slide some windows? Head to Solve LeetCode 480 on LeetCode and track it today—your coding skills are median-ready!