Sliding Window Median - Practice Coding Problems

Sliding Window Median - 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 example, if arr = [2, 3, 4], the median is 3.

For example, 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⁻⁵ of the actual value will be accepted.

Input & Output

Example 1 — Basic Case

$ 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]

💡 Note: Window [1,3,-1] → sorted [-1,1,3] → median 1.0. Window [3,-1,-3] → sorted [-3,-1,3] → median -1.0. Continue for all windows.

Example 2 — Even Window Size

$ Input: nums = [1,2,3,4], k = 2

› Output: [1.5,2.5,3.5]

💡 Note: 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 — Single Element Window

$ Input: nums = [1,4,2,3], k = 1

› Output: [1.0,4.0,2.0,3.0]

💡 Note: Each window contains one element, so median equals that element: 1.0, 4.0, 2.0, 3.0.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length
-2³¹ ≤ nums[i] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,-1,-3,5,3,6,7] with window size k=3

Process

Slide window and find median of each k-sized subarray

Output

Array of medians [1.0,-1.0,-1.0,3.0,5.0,6.0]

Key Takeaway

🎯 Key Insight: Use sliding window to process each k-sized subarray and find median efficiently

Asked in

G Google 42 f Facebook 38 a Amazon 35 M Microsoft 28

The key insight is to use two balanced heaps to maintain the median efficiently as the window slides. The brute force approach sorts each window in O(n×k log k) time, while the optimized two-heap approach achieves O(n log k) by maintaining sorted halves. Best approach uses max-heap for smaller elements, min-heap for larger elements. Time: O(n log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Sort Each Window	O(n × k log k)	O(k)	Sort each window of size k to find median
Two Heaps Optimization	O(n log k)	O(k)	Use max-heap and min-heap to maintain median efficiently

Brute Force - Sort Each Window — Algorithm Steps

For each window position, extract k elements
Sort the window elements
Find median from sorted window
Add median to result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Window 1

Extract first k elements and sort

Window 2

Move window right, extract and sort again

Continue

Repeat for all positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

double* solution(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = numsSize - k + 1;
    double* result = (double*)malloc(*returnSize * sizeof(double));
    
    for (int i = 0; i <= numsSize - k; i++) {
        int* window = (int*)malloc(k * sizeof(int));
        for (int j = 0; j < k; j++) {
            window[j] = nums[i + j];
        }
        qsort(window, k, sizeof(int), compare);
        
        double median;
        if (k % 2 == 1) {
            median = window[k / 2];
        } else {
            median = (window[k / 2 - 1] + window[k / 2]) / 2.0;
        }
        
        result[i] = median;
        free(window);
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char *token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    double* result = solution(nums, numsSize, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%g", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k log k)

For each of n-k+1 windows, we sort k elements taking O(k log k)

⚡ Linearithmic

Space Complexity

O(k)

Extra array to store window elements for sorting

✓ Linear Space

78.0K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Sort Each Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler