Sliding Window Median - Solution & Explanation

Q: Is Sliding Window Median easy or hard?

Sliding Window Median is classified as a hard problem because it requires combining sliding window logic with advanced data structures like heaps or balanced trees. Managing deletions and maintaining median balance makes the implementation tricky.

Q: Sliding Window Median Python or Java solution

Python solutions usually rely on two heaps using the heapq module with lazy deletion through a dictionary. Java implementations often use PriorityQueue or TreeMap structures to maintain ordered elements and compute medians efficiently.

Q: How to solve Sliding Window Median in O(n log k)?

Use two heaps to keep track of the smaller and larger halves of the current window. Insert the incoming element into the correct heap, mark outgoing elements for lazy deletion, and rebalance the heaps so their sizes differ by at most one. The median is always available from the heap tops.

Q: What is the best approach for Sliding Window Median?

The dual heap approach is the most common optimal solution. It maintains two heaps: a max heap for the lower half and a min heap for the upper half of the window. With lazy deletion for elements leaving the window, each update costs O(log k), giving an overall complexity of O(n log k).

Q: What data structure is used in Sliding Window Median?

The most common data structures are two heaps (a max heap and a min heap) combined with a hash map for lazy deletion. Alternative implementations use balanced binary search trees such as multiset or TreeMap-based structures.

Q: What is the time complexity of Sliding Window Median?

The optimal solutions run in O(n log k) time where n is the array size and k is the window size. Each insertion or removal from the heaps or balanced tree takes O(log k). The brute force approach that sorts each window costs O(n * k log k).

Q: Is Sliding Window Median asked at Google Amazon or Meta?

Sliding Window Median is considered a classic hard interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests heap usage, balancing logic, and efficient sliding window updates.

HardArray Hash Table Sliding Window Heap (Priority Queue)39 min readAsked at: Amazon, Microsoft, Apple +8

Practice this problem

Problem Statement

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 examples, if arr = [2,3,4], the median is 3.
For examples, 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^-5 of the actual value will be accepted.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

Example 2:

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array and a window size k. As the window slides one step to the right, compute the median of the current window. The challenge is maintaining the median efficiently while elements enter and leave the window.

Approach 1: Brute Force (O(n * k log k) time, O(k) space)

The most direct approach recomputes the median for every window. Extract the k elements in the current window, sort them, and read the middle element (or the average of two middle elements for even k). Sorting costs O(k log k) per window and there are about n - k + 1 windows, resulting in O(n * k log k) time. Space complexity is O(k) to hold the temporary window. This approach is easy to implement and useful for verifying correctness, but it becomes slow when k grows large.

Approach 2: Dual Heap Approach (O(n log k) time, O(k) space)

This is the standard optimal solution. Maintain two heaps: a max heap for the smaller half of numbers and a min heap for the larger half. The heaps stay balanced so their sizes differ by at most one, allowing the median to be read directly from the heap tops. When the window slides, insert the new element and lazily remove the outgoing element using a hash map to track delayed deletions. Each insertion or removal costs O(log k), so processing all elements takes O(n log k) time. This technique combines heap (priority queue) operations with a small hash table for efficient cleanup.

Approach 3: Heap-Based Sliding Window with Lazy Deletion (O(n log k) time, O(k) space)

A variation of the dual heap approach explicitly focuses on lazy deletion. Instead of removing elements immediately when they fall out of the window, mark them in a map and clean them only when they appear at the top of a heap. This avoids expensive arbitrary deletions from a heap. The heaps maintain balance as elements are inserted and invalid ones are popped. Median lookup remains O(1). This method is widely used in competitive programming for sliding window median problems.

Approach 4: Multiset and Iterator (O(n log k) time, O(k) space)

Languages with ordered containers (like multiset in C++ or TreeSet-like structures) allow a different strategy. Store the current window in a balanced binary search tree and maintain an iterator pointing to the median element. When the window moves, insert the incoming value and erase the outgoing one while adjusting the iterator accordingly. Both operations take O(log k). Accessing the median becomes constant time. This approach is clean and deterministic but relies on ordered-set support.

Recommended for interviews: The dual heap approach is what most interviewers expect. It demonstrates understanding of heap balancing, lazy deletion, and sliding window optimization. Showing the brute force first proves you understand the problem, but implementing the O(n log k) heap solution demonstrates strong data structure skills.

Approach 1: Dual Heap Approach

The dual heap approach uses two heaps to maintain the sliding window median. The idea is to maintain a max heap for the left half of the data and a min heap for the right half. This allows for efficient retrieval of the median at any point:

Use a max heap to store the smaller half of the numbers (lower part).
Use a min heap to store the larger half of the numbers (upper part).
When the window slides, update these heaps accordingly.
The median can be extracted as the maximum from the max heap or by averaging the top of both heaps, depending on the window size (odd/even).

This Python solution uses the `SortedList` from the `sortedcontainers` module to maintain an ordered list of numbers in the current window. As the window slides:

We add the new number and remove the one that's slid out.
The list remains sorted, allowing easy median computation.
The `SortedList` maintains order efficiently, ensuring operations stay logarithmic in nature.

Code

Python

Complexity

Time Complexity: O(n log k), where n is the number of elements in nums and k is the window size because insertion and deletion in a SortedList take O(log k) time.

Space Complexity: O(k) because we store at most k elements in the SortedList.

Try this approach in the editor →

Approach 2: Brute Force Approach

This approach iteratively computes the median for each possible window by sorting the window at each step. This is a simpler approach but less efficient:

For each window, extract the subarray.
Sort this subarray to find the median.
Move the window one element to the right and repeat.

This straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:

Sort the subarray extracted from nums starting at the current index.
Compute the median based on the parity of k.
Collect computed medians for all possible windows.

Code

Python

Complexity

Time Complexity: O(nk log k) due to sorting each subarray of size k for every possible window.

Space Complexity: O(k) to store the current window’s elements temporarily.

Try this approach in the editor →

Approach 3: Heap-Based Approach

Use two heaps: a max-heap to keep track of the lower half of the window and a min-heap for the upper half. The max-heap stores the smaller half of numbers, while the min-heap stores the larger half. By maintaining the size property (balance) of these heaps, we can always pull the median based on the size of the window:

When the sizes of both heaps are equal, the median is the mean of the top elements of both heaps.
When the size of the max-heap is greater than the min-heap, the median is the top of the max-heap.

Efficient insertion and removal using heaps make this approach suitable for large inputs.

This solution defines three core functions: add_number to handle numbers entering the heap, remove_number deals with numbers leaving the heap, and balance_heaps keeps the two heaps balanced. The median is calculated based on the sizes of the heaps after adjusting them.

Code

Python C++

Python

C++

Complexity

Time Complexity: O(n * log k), due to heap operations per window.

Space Complexity: O(k), for storing elements in the heaps.

Try this approach in the editor →

Approach 4: Multiset and Iterator Approach

Using a balanced binary search tree structure (like C++ STL's multiset) that maintains order can help efficiently find medians. This approach utilizes iterators, which allow seamless tracking of median positions as we move the sliding window:

Elements are inserted and removed from the multiset while the iterator always points to the median or close to it.
The iterator is adjusted based on the balance between the lower and upper halves.

This Java implementation utilizes a TreeMap to store the elements of the current window. Functions to add and remove elements adjust the frequency count within the set, allowing us to maintain window data. getMedian then determines the median based on the current state of the window.

Code

Java C#

Java

Complexity

Time Complexity: O(n * log k), due to tree operations within each window adjustment.

Space Complexity: O(k), for tracking window elements within the tree.

Try this approach in the editor →

Approach 5: Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion

We can use two priority queues (min-heap and max-heap) to maintain the elements in the current window. One priority queue stores the smaller half of the elements, and the other priority queue stores the larger half of the elements. This way, the median of the current window is either the average of the top elements of the two heaps or one of the top elements.

We design a class MedianFinder to maintain the elements in the current window. This class includes the following methods:

add_num(num): Adds num to the current window.
find_median(): Returns the median of the elements in the current window.
remove_num(num): Removes num from the current window.
prune(pq): If the top element of the heap is in the lazy deletion dictionary delayed, it pops the top element from the heap and decrements its lazy deletion count. If the lazy deletion count of the element becomes zero, it removes the element from the lazy deletion dictionary.
rebalance(): If the number of elements in the smaller half exceeds the number of elements in the larger half by 2, it moves the top element of the larger half to the smaller half. If the number of elements in the smaller half is less than the number of elements in the larger half, it moves the top element of the larger half to the smaller half.

In the add_num(num) method, we first consider adding num to the smaller half. If num is greater than the top element of the larger half, we add num to the larger half. Then we call the rebalance() method to ensure that the size difference between the two priority queues does not exceed 1.

In the remove_num(num) method, we increment the lazy deletion count of num. Then we compare num with the top element of the smaller half. If num is less than or equal to the top element of the smaller half, we update the size of the smaller half and call the prune() method to ensure that the top element of the smaller half is not in the lazy deletion dictionary. Otherwise, we update the size of the larger half and call the prune() method to ensure that the top element of the larger half is not in the lazy deletion dictionary.

In the find_median() method, if the current window size is odd, we return the top element of the smaller half; otherwise, we return the average of the top elements of the smaller half and the larger half.

In the prune(pq) method, if the top element of the heap is in the lazy deletion dictionary, it pops the top element from the heap and decrements its lazy deletion count. If the lazy deletion count of the element becomes zero, it removes the element from the lazy deletion dictionary.

In the rebalance() method, if the number of elements in the smaller half exceeds the number of elements in the larger half by 2, it moves the top element of the larger half to the smaller half. If the number of elements in the smaller half is less than the number of elements in the larger half, it moves the top element of the larger half to the smaller half.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Approach 6: Ordered Set

We can use two ordered sets to maintain the elements in the current window. The ordered set l stores the smaller half of the elements in the current window, and the ordered set r stores the larger half of the elements.

We traverse the array nums. For each element x, we add it to the ordered set r, then move the smallest element in the ordered set r to the ordered set l. If the size of the ordered set l is greater than the size of the ordered set r by more than 1, we move the largest element in the ordered set l to the ordered set r.

If the total number of elements in the current window is k and the size is odd, the maximum value in the ordered set l is the median. If the size of the current window is even, the average of the maximum value in the ordered set l and the minimum value in the ordered set r is the median. Then, we remove the leftmost element of the window and continue traversing the array.

The time complexity is O(n log k), and the space complexity is O(k). Here, n is the length of the array nums.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Dual Heap Approach	Time Complexity: O(n log k), where n is the number of elements in nums and k is the window size because insertion and deletion in a SortedList take O(log k) time. Space Complexity: O(k) because we store at most k elements in the SortedList.
Brute Force Approach	Time Complexity: O(nk log k) due to sorting each subarray of size k for every possible window. Space Complexity: O(k) to store the current window’s elements temporarily.
Heap-Based Approach	Time Complexity: O(n * log k), due to heap operations per window. Space Complexity: O(k), for storing elements in the heaps.
Multiset and Iterator Approach	Time Complexity: O(n * log k), due to tree operations within each window adjustment. Space Complexity: O(k), for tracking window elements within the tree.
Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion	—
Ordered Set	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Sorting	O(n * k log k)	O(k)	Small window sizes or quick correctness check
Dual Heap (Max Heap + Min Heap)	O(n log k)	O(k)	General optimal solution for interviews and production
Heap with Lazy Deletion	O(n log k)	O(k)	When implementing sliding window medians efficiently with priority queues
Multiset / Balanced BST	O(n log k)	O(k)	Languages with ordered sets like C++ or Java Tree structures

Video Solution

LeetCode - Sliding Window Median (480) • Kshittiz K • 20,496 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sliding Window Median easy or hard?

Sliding Window Median is classified as a hard problem because it requires combining sliding window logic with advanced data structures like heaps or balanced trees. Managing deletions and maintaining median balance makes the implementation tricky.

Sliding Window Median Python or Java solution

Python solutions usually rely on two heaps using the heapq module with lazy deletion through a dictionary. Java implementations often use PriorityQueue or TreeMap structures to maintain ordered elements and compute medians efficiently.

How to solve Sliding Window Median in O(n log k)?

Use two heaps to keep track of the smaller and larger halves of the current window. Insert the incoming element into the correct heap, mark outgoing elements for lazy deletion, and rebalance the heaps so their sizes differ by at most one. The median is always available from the heap tops.

What is the best approach for Sliding Window Median?

The dual heap approach is the most common optimal solution. It maintains two heaps: a max heap for the lower half and a min heap for the upper half of the window. With lazy deletion for elements leaving the window, each update costs O(log k), giving an overall complexity of O(n log k).

What data structure is used in Sliding Window Median?

The most common data structures are two heaps (a max heap and a min heap) combined with a hash map for lazy deletion. Alternative implementations use balanced binary search trees such as multiset or TreeMap-based structures.

What is the time complexity of Sliding Window Median?

The optimal solutions run in O(n log k) time where n is the array size and k is the window size. Each insertion or removal from the heaps or balanced tree takes O(log k). The brute force approach that sorts each window costs O(n * k log k).

Is Sliding Window Median asked at Google Amazon or Meta?

Sliding Window Median is considered a classic hard interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests heap usage, balancing logic, and efficient sliding window updates.

Ready to solve this problem?

Practice Sliding Window Median with our built-in code editor and test cases.

Practice on FleetCode

Find Median from Data Stream

Minimum Operations to Make Median of Array Equal to K

Problem Info

DifficultyHard

Acceptance38.7%

Approaches6

Reading time39 min

Asked at

Amazon Microsoft Apple Meta Salesforce

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Dual Heap Approach

Code

Complexity

Approach 2: Brute Force Approach

Code

Complexity

Approach 3: Heap-Based Approach

Code

Complexity

Approach 4: Multiset and Iterator Approach

Code

Complexity

Approach 5: Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion

Code

Approach 6: Ordered Set

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents