Sliding Window Median

Problem Statement

Given an array and a window size k, find the median of each sliding window.

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

Approach 1: Sort Each Window

Explanation: Naive approach: sort each window and pick median.

Time Complexity: O(n k log k)

Space Complexity: O(k)

        for i in 0..n-k:
            window = nums[i..i+k-1]
            sort(window)
            median = window[k//2]
            add median to result
        return result
Heap Sort Flowchart