Practice/Meta/Leetcode 480. Sliding Window Median

Leetcode 480. Sliding Window Median

CodingMust

Problem

You are given an array of integers and a window size k. Your task is to slide a fixed-size window from left to right across the array, one position at a time, and compute the median value within each window position.

Return an array containing the median for each window position. When the window size is even, the median should be calculated as the average of the two middle elements.

Requirements

1. Process each window from left to right, starting at index 0
2. For odd k, return the middle element as the median
3. For even k, return the average of the two middle elements
4. Return results as an array of floating-point numbers
5. Handle duplicate values correctly

Constraints

• 1 ≤ nums.length ≤ 100,000
• 1 ≤ k ≤ nums.length
• -2³¹ ≤ nums[i] ≤ 2³¹ - 1
• Target time complexity: O(n log k) where n is the array length
• Target space complexity: O(k) for the window data structure

Examples

Example 1:

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] Explanation: Window [1, 3, -1] → sorted: [-1, 1, 3] → median: 1 Window [3, -1, -3] → sorted: [-3, -1, 3] → median: -1 Window [-1, -3, 5] → sorted: [-3, -1, 5] → median: -1 Window [-3, 5, 3] → sorted: [-3, 3, 5] → median: 3 Window [5, 3, 6] → sorted: [3, 5, 6] → median: 5 Window [3, 6, 7] → sorted: [3, 6, 7] → median: 6

Example 2:

Input: nums = [1, 2, 3, 4], k = 2 Output: [1.5, 2.5, 3.5] Explanation: Window [1, 2] → median: (1 + 2) / 2 = 1.5 Window [2, 3] → median: (2 + 3) / 2 = 2.5 Window [3, 4] → median: (3 + 4) / 2 = 3.5

Example 3:

Input: nums = [5], k = 1 Output: [5.0] Explanation: Single element is its own median