Skip to main content

Sliding Window Median

Question​

What is the most efficient algorithm for finding the median of a sliding window of size 'n' in an unsorted array of integers?

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

Output: [1,-1,-1,3,5,6]

Solution​

all//Sliding Window Median.py


def sliding_window_median(arr, k):
    medianlist = []

    # Consider all windows one by one
    for i in range(len(arr)-k+1):
        # Get a window of size k
        window = arr[i:i+k]

        # Sort the window
        window.sort()

        # Find median
        mid_index = int((k - 1)/2)
        medianlist.append(window[mid_index])

    return medianlist

# Driver code
arr = [1, 2, 3, 4, 5, 6, 7]
k = 3
print(sliding_window_median(arr, k))
# Output: [2, 3, 4, 5]