> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Sliding Window Median Python Solution

> Tested Python solution for LeetCode 480 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 480, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Sliding Window](/catalog/topics/sliding-window), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), Treap. [View on LeetCode](https://leetcode.com/problems/sliding-window-median/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 480   # by problem number
lcpy gen -s sliding_window_median   # by problem name
```

## Problem

The **median** is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

* For examples, if `arr = [2,**3**,4]`, the median is `3`.
* For examples, if `arr = [1,**2,3**,4]`, the median is `(2 + 3) / 2 = 2.5`.

You are given an integer array `nums` and an integer `k`. There is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position.

Return *the median array for each window in the original array*. Answers within `10^-5` of the actual value will be accepted.

### Examples

```
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
```

**Explanation:**

Window position                Median

***

\[1  3  -1] -3  5  3  6  7        1
1 \[3  -1  -3] 5  3  6  7       -1
1  3 \[-1  -3  5] 3  6  7       -1
1  3  -1 \[-3  5  3] 6  7        3
1  3  -1  -3 \[5  3  6] 7        5
1  3  -1  -3  5 \[3  6  7]       6

```
Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sliding_window_median/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sliding_window_median/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log n) - each element is pushed and popped a constant number of times
    # Space: O(n) - two heaps plus the delayed-deletion counter
    def median_sliding_window(self, nums: list[int], k: int) -> list[float]:
        small: list[int] = []  # max-heap (negated values), holds the lower half
        large: list[int] = []  # min-heap, holds the upper half
        delayed: dict[int, int] = {}
        small_size = 0
        large_size = 0
        medians: list[float] = []

        def prune(heap: list[int]) -> None:
            sign = -1 if heap is small else 1
            while heap:
                top = sign * heap[0]
                if top not in delayed:
                    break
                delayed[top] -= 1
                if delayed[top] == 0:
                    del delayed[top]
                heapq.heappop(heap)

        def rebalance() -> None:
            nonlocal small_size, large_size
            if small_size > large_size + 1:
                heapq.heappush(large, -small[0])
                heapq.heappop(small)
                small_size -= 1
                large_size += 1
                prune(small)
            elif small_size < large_size:
                heapq.heappush(small, -large[0])
                heapq.heappop(large)
                small_size += 1
                large_size -= 1
                prune(large)

        def insert(num: int) -> None:
            nonlocal small_size, large_size
            if not small or num <= -small[0]:
                heapq.heappush(small, -num)
                small_size += 1
            else:
                heapq.heappush(large, num)
                large_size += 1
            rebalance()

        def erase(num: int) -> None:
            nonlocal small_size, large_size
            delayed[num] = delayed.get(num, 0) + 1
            if num <= -small[0]:
                small_size -= 1
                if num == -small[0]:
                    prune(small)
            else:
                large_size -= 1
                if num == large[0]:
                    prune(large)
            rebalance()

        def median() -> float:
            if k % 2 == 1:
                return float(-small[0])
            return (-small[0] + large[0]) / 2

        for num in nums[:k]:
            insert(num)
        medians.append(median())

        for i in range(k, len(nums)):
            insert(nums[i])
            erase(nums[i - k])
            medians.append(median())

        return medians
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) - each element is pushed and popped a constant number of times | O(n) - two heaps plus the delayed-deletion counter |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.