What happens if you sorting each window without optimization?

Solution times out on large inputs Fix: Use two heaps or balanced trees to maintain median efficiently

What happens if you not handling lazy removals correctly in heaps?

Median calculation becomes incorrect or code crashes Fix: Implement lazy removal with a hash map and prune heaps properly

What happens if you incorrect balancing of heaps sizes?

Median is wrong because heaps are unbalanced Fix: Ensure heaps differ in size by at most one after every insertion/removal

What happens if you ignoring even k median calculation?

Returns wrong median for even-sized windows Fix: Return average of two middle elements when k is even

Interview Preptwo-heapsmediumAmazonGoogle

Maximum Sliding Window Median

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumHEAPAmazonGoogle

Imagine monitoring the median price of a stock over the last k minutes as new prices stream in every second. You want to quickly know the median price in the current window to make trading decisions.

💡 This problem involves maintaining a median dynamically as the window slides over an array. Beginners often struggle because median is not a simple max or min, and updating medians efficiently requires a clever data structure approach rather than naive sorting each time.

📋

Problem Statement

Given an integer array nums and an integer k, find the median of every contiguous subarray of size k. Return an array of these medians. The median is the middle element after sorting the window if k is odd, or the average of the two middle elements if k is even.

1 ≤ nums.length ≤ 10^51 ≤ k ≤ nums.length-10^7 ≤ nums[i] ≤ 10^7

💡

Example

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

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

The sliding windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]. Their medians are 1, -1, -1, 3, 5, 6 respectively.

k = 1 → median is each element itself
All elements are the same → median equals that element
k equals nums.length → median of entire array
Array with negative and positive numbers mixed

⚠️

Common Mistakes

Sorting each window without optimization

Solution times out on large inputs

✅ Use two heaps or balanced trees to maintain median efficiently

Not handling lazy removals correctly in heaps

Median calculation becomes incorrect or code crashes

✅ Implement lazy removal with a hash map and prune heaps properly

Incorrect balancing of heaps sizes

Median is wrong because heaps are unbalanced

✅ Ensure heaps differ in size by at most one after every insertion/removal

Ignoring even k median calculation

Returns wrong median for even-sized windows

✅ Return average of two middle elements when k is even

Using data structures without efficient removal support

Code becomes complex or inefficient

✅ Choose data structures like balanced BST or implement lazy removal

🧠

Brute Force (Sort Each Window)

💡 This approach exists to build intuition by directly implementing the problem definition. It is simple but inefficient, helping beginners understand the median concept and sliding window mechanics.

Intuition

For each window of size k, extract the subarray, sort it, and find the median. Repeat for all windows.

Algorithm

Iterate over all windows of size k in the array.
For each window, copy the elements into a temporary list.
Sort the temporary list.
Calculate the median from the sorted list and add it to the result.

💡 The main challenge is realizing that sorting each window is repetitive and costly, but it directly follows the problem statement.

</>

Code

from typing import List

def median_of_sorted(arr: List[int]) -> float:
    n = len(arr)
    mid = n // 2
    if n % 2 == 1:
        return float(arr[mid])
    else:
        return (arr[mid - 1] + arr[mid]) / 2

def max_sliding_window_median(nums: List[int], k: int) -> List[float]:
    n = len(nums)
    result = []
    for i in range(n - k + 1):
        window = nums[i:i+k]
        window.sort()
        med = median_of_sorted(window)
        result.append(med)
    return result

# Driver code
if __name__ == '__main__':
    nums = [1,3,-1,-3,5,3,6,7]
    k = 3
    print(max_sliding_window_median(nums, k))

Line Notes

def median_of_sorted(arr: List[int]) -> float:Helper function to compute median from a sorted list

window = nums[i:i+k]Extract current window slice from the array

window.sort()Sort the window to find median easily

result.append(med)Store the median for the current window

import java.util.*;

public class SlidingWindowMedian {
    public static double medianOfSorted(List<Integer> arr) {
        int n = arr.size();
        int mid = n / 2;
        if (n % 2 == 1) {
            return (double) arr.get(mid);
        } else {
            return (arr.get(mid - 1) + arr.get(mid)) / 2.0;
        }
    }

    public static List<Double> maxSlidingWindowMedian(int[] nums, int k) {
        List<Double> result = new ArrayList<>();
        for (int i = 0; i <= nums.length - k; i++) {
            List<Integer> window = new ArrayList<>();
            for (int j = i; j < i + k; j++) {
                window.add(nums[j]);
            }
            Collections.sort(window);
            result.add(medianOfSorted(window));
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println(maxSlidingWindowMedian(nums, k));
    }
}

Line Notes

public static double medianOfSorted(List<Integer> arr)Helper method to find median from sorted list

for (int i = 0; i <= nums.length - k; i++)Iterate over all windows starting indices

Collections.sort(window);Sort current window to find median

result.add(medianOfSorted(window));Add median of current window to results

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

double medianOfSorted(const vector<int>& arr) {
    int n = arr.size();
    int mid = n / 2;
    if (n % 2 == 1) {
        return (double)arr[mid];
    } else {
        return (arr[mid - 1] + arr[mid]) / 2.0;
    }
}

vector<double> maxSlidingWindowMedian(const vector<int>& nums, int k) {
    vector<double> result;
    int n = nums.size();
    for (int i = 0; i <= n - k; i++) {
        vector<int> window(nums.begin() + i, nums.begin() + i + k);
        sort(window.begin(), window.end());
        result.push_back(medianOfSorted(window));
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<double> res = maxSlidingWindowMedian(nums, k);
    for (double val : res) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

double medianOfSorted(const vector<int>& arr)Calculate median from sorted vector

vector<int> window(nums.begin() + i, nums.begin() + i + k);Copy current window elements

sort(window.begin(), window.end());Sort window to find median

result.push_back(medianOfSorted(window));Append median to result vector

function medianOfSorted(arr) {
    const n = arr.length;
    const mid = Math.floor(n / 2);
    if (n % 2 === 1) {
        return arr[mid];
    } else {
        return (arr[mid - 1] + arr[mid]) / 2;
    }
}

function maxSlidingWindowMedian(nums, k) {
    const result = [];
    for (let i = 0; i <= nums.length - k; i++) {
        const window = nums.slice(i, i + k);
        window.sort((a, b) => a - b);
        result.push(medianOfSorted(window));
    }
    return result;
}

// Test
const nums = [1,3,-1,-3,5,3,6,7];
const k = 3;
console.log(maxSlidingWindowMedian(nums, k));

Line Notes

function medianOfSorted(arr)Helper to compute median from sorted array

const window = nums.slice(i, i + k);Extract current sliding window

window.sort((a, b) => a - b);Sort window to find median

result.push(medianOfSorted(window));Add median to output array

⏱

Complexity

TimeO(n * k log k)

SpaceO(k)

For each of the n-k+1 windows, sorting k elements costs O(k log k), leading to O(n k log k) total time. Space is O(k) for the temporary window.

💡 For n=1000 and k=100, this means about 1000 * 100 * 7 = 700,000 operations, which is slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and median calculation before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n k log k)`	`O(k)`	No	N/A	Mention only - never code
2. Two Heaps with Lazy Removal	`O(n log k)`	`O(k)`	No	Yes	Code this approach in interviews
3. Balanced BST / Sorted Array with Binary Search	`O(n k)`	`O(k)`	No	Yes	Good alternative if language supports balanced trees

Practice

(1/5)

1. Given the following code and input, what is the final output printed?

import heapq

MOD = 10**9 + 7

def maxPerformance(n, speed, efficiency, k):
    engineers = sorted(zip(efficiency, speed), key=lambda x: -x[0])
    max_perf = 0
    speed_heap = []
    sum_speed = 0
    for eff, spd in engineers:
        heapq.heappush(speed_heap, spd)
        sum_speed += spd
        if len(speed_heap) > k:
            sum_speed -= heapq.heappop(speed_heap)
        max_perf = max(max_perf, sum_speed * eff)
    return max_perf % MOD

if __name__ == '__main__':
    n = 3
    speed = [2, 8, 4]
    efficiency = [3, 1, 2]
    k = 2
    print(maxPerformance(n, speed, efficiency, k))

easy

A. 24

B. 20

C. 30

D. 18

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Sort engineers by efficiency descending

Step 2: Iterate and maintain min-heap of speeds with max size k=2

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Evaluate algorithmic approaches

Final Answer:

Quick Check:

Solution

Step 1: Analyze heap insertions and removals

Step 2: Analyze K iterations

Final Answer:

Quick Check:

Solution

Step 1: Analyze heap operations

Step 2: Count total operations

Final Answer:

Quick Check:

Solution

Step 1: Identify operations per task

Step 2: Analyze hash map operations

Final Answer:

Quick Check:

Ready to prove it?