Solution: Sliding Window Median

Statement

Given an integer array, nums, and an integer, k, there is a sliding window of size k, which is moving from the very left to the very right of the array. We can only see the k numbers in the window. Each time the sliding window moves right by one position.

Given this scenario, return the median of the each window. Answers within $10^{-5}$ of the actual value will be accepted.

Constraints:

• $1 \leq$ k $\leq$ nums.length $\leq 10^3$
• $-2^{31} \leq$ nums[i] $\leq 2^{31} - 1$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive solution is to use nested loops to traverse over the array. The outer loop ranges over the entire array, and the nested loop is used to iterate over windows of $k$ elements. For each window, we’ll first sort the elements and then compute the median. We’ll append this value to the median list and move the window one step forward.

The above algorithm will have a total time complexity of $O(n - k + 1) \cdot O(k \log k)$ ...