use SortedList to maintain window in sorted order. initialize with first k elements. for each new element, remove leftmost (nums[i-k]) and add new element (nums[i]). calculate median from sorted list.
median calculation: if k is odd, return middle element. if k is even, return average of two middle elements. SortedList provides O(log k) insert/remove operations.
approach
- initialize SortedList with first k elements
- calculate median for initial window
- for each new element: remove old, add new, recalculate median
- SortedList maintains order automatically
complexity
O(n log k) time where n is array length and k is window size. O(k) space for sorted list.