What is the time complexity of Sliding Window Median?

The optimal solution has a time complexity of O(n log k).

What data structures are used to solve Sliding Window Median?

This problem uses Array, Hash Table, Sliding Window, Heap (Priority Queue). Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Sliding Window Median?

Insight 1: Using two heaps (a min-heap and a max-heap) allows efficient tracking of the window's elements and finding the median without sorting the window in each step. Insight 2: A crucial optimization is to use a `to_remove` map to handle elements that are no longer in the sliding window. This avoids directly removing elements from the heaps, which would be an O(k) operation, significantly improving performance.

Which companies ask LeetCode 480. Sliding Window Median in interviews?

This problem is frequently asked at Datadog, DoorDash, Flipkart, Point72, Snowflake.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Sliding Window Median - LeetCode 480 Solution

Sliding Window Median - Complete Solution Guide

Sliding Window Median is LeetCode problem 480, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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. Ea

Detailed Explanation

The problem asks us to find the median of a sliding window of size `k` as it moves across an array `nums`. The window moves one position at a time, and we need to return an array containing the median value for each window position. The median is the middle element when the elements in the window are sorted. If the window size `k` is even, the median is the average of the two middle elements.

Solution Approach

The solution uses two heaps: a max-heap (`lo`) to store the smaller half of the elements in the current window and a min-heap (`hi`) to store the larger half. The max-heap's root will always be the largest value in the smaller half, and the min-heap's root will always be the smallest value in the larger half. This arrangement allows for efficient calculation of the median. When the window slides, we remove the outgoing element and add the incoming element while maintaining the heap balance. A hashmap `to_remove` is used to track elements that need to be removed from the heaps. The balancing is done to ensure that the sizes of the heaps are either equal (if `k` is even) or the max-heap has one more element (if `k` is odd). This enables calculating the median in O(1) time by looking at the top elements of the heaps.

Step-by-Step Algorithm

Step 1: Initialize two heaps: `lo` (max-heap) and `hi` (min-heap). Also, initialize a hash map `to_remove` to keep track of elements to be removed.
Step 2: Fill the initial window (first `k` elements) into the heaps. Push the first `k` elements into the max-heap `lo`. Then move the smallest `k // 2` elements from `lo` to the min-heap `hi` to balance them initially.
Step 3: Calculate the median of the first window. If `k` is odd, the median is the top element of `lo`. If `k` is even, the median is the average of the top elements of `lo` and `hi`.
Step 4: Iterate through the rest of the array (from index `k` to `nums.length - 1`).
Step 5: For each iteration, remove the element that's leaving the window (`out_num`) and add the new element that's entering the window (`in_num`). Update the `to_remove` map with the `out_num`.
Step 6: Based on whether `out_num` and `in_num` should belong to the `lo` or `hi` heap, update the heap and calculate the `balance` (difference in sizes) after each operation
Step 7: Rebalance the heaps to maintain the property that `lo` has either the same number of elements as `hi` (if `k` is even) or one more (if `k` is odd).
Step 8: Clean the heap's tops by removing delayed deletions, ensuring that any delayed deletions present at the top are cleared from both heaps. Delayed deletions are maintained within a hashmap.
Step 9: Calculate the median of the current window as in step 3 and add it to the result.
Step 10: Repeat steps 5-9 until the end of the `nums` array.

Key Insights

Insight 1: Using two heaps (a min-heap and a max-heap) allows efficient tracking of the window's elements and finding the median without sorting the window in each step.
Insight 2: A crucial optimization is to use a `to_remove` map to handle elements that are no longer in the sliding window. This avoids directly removing elements from the heaps, which would be an O(k) operation, significantly improving performance.
Insight 3: Balancing the heaps to maintain the median efficiently is crucial. The max-heap stores the smaller half of the elements, and the min-heap stores the larger half. Maintaining this balance after each window slide is essential for O(1) median retrieval.

Complexity Analysis

Time Complexity: O(n log k)

Space Complexity: O(k)

Topics

This problem involves: Array, Hash Table, Sliding Window, Heap (Priority Queue).

Companies

Asked at: Datadog, DoorDash, Flipkart, Point72, Snowflake.

Sliding Window Median | LeetCode 480

Hard

Array Hash Table Sliding Window Heap (Priority Queue)

Time: O(n log k)Space: O(k)

Solution Code

Available in:

import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // lo is max-heap
        PriorityQueue<Integer> hi = new PriorityQueue<>(); // hi is min-heap

        for (int i = 0; i < k; i++) {
            lo.add(nums[i]);
        }
        for (int i = 0; i < k / 2; i++) {
            hi.add(lo.poll());
        }

        List<Double> resultList = new ArrayList<>();
        Map<Integer, Integer> toRemove = new HashMap<>();

        // First median
        if (k % 2 == 1) {
            resultList.add((double) lo.peek());
        } else {
            resultList.add(((double) lo.peek() + hi.peek()) / 2.0);
        }

        for (int i = k; i < nums.length; i++) {
            int outNum = nums[i - k];
            int inNum = nums[i];
            int balance = 0;

            // Determine imbalance caused by removing outNum
            // The top of lo serves as the pivot to divide the two halves
            if (outNum <= lo.peek()) {
                balance -= 1;
            } else {
                balance += 1;
            }
            toRemove.put(outNum, toRemove.getOrDefault(outNum, 0) + 1);

            // Add inNum and update imbalance
            if (!lo.isEmpty() && inNum <= lo.peek()) {
                lo.add(inNum);
                balance += 1;
            } else {
                hi.add(inNum);
                balance -= 1;
            }

            // Rebalance heaps based on imbalance
            if (balance > 0) { // lo is conceptually larger
                hi.add(lo.poll());
            } else if (balance < 0) { // hi is conceptually larger
                lo.add(hi.poll());
            }

            // Clean invalid elements from heap tops
            while (!lo.isEmpty() && toRemove.getOrDefault(lo.peek(), 0) > 0) {
                int top = lo.poll();
                toRemove.put(top, toRemove.get(top) - 1);
                if (toRemove.get(top) == 0){
                    toRemove.remove(top);
                }

            }
            while (!hi.isEmpty() && toRemove.getOrDefault(hi.peek(), 0) > 0) {
                int top = hi.poll();
                toRemove.put(top, toRemove.get(top) - 1);
                if (toRemove.get(top) == 0){
                    toRemove.remove(top);
                }
            }

            // Calculate new median
            if (k % 2 == 1) {
                resultList.add((double) lo.peek());
            } else {
                resultList.add(((double) lo.peek() + hi.peek()) / 2.0);
            }
        }

        double[] result = new double[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 480: Sliding Window Median - Detailed explanation and solution approaches.

Topics

Array Hash Table Sliding Window Heap (Priority Queue)

Companies

DatadogDoorDashFlipkartPoint72Snowflake

Stats

Difficulty:Hard

Languages:4

Companies:5

Problem #:480

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize two heaps: `lo` (max-heap) and `hi` (min-heap). Also, initialize a hash map `to_remove` to keep track of elements to be removed.
2
Step 2: Fill the initial window (first `k` elements) into the heaps. Push the first `k` elements into the max-heap `lo`. Then move the smallest `k // 2` elements from `lo` to the min-heap `hi` to balance them initially.
3
Step 3: Calculate the median of the first window. If `k` is odd, the median is the top element of `lo`. If `k` is even, the median is the average of the top elements of `lo` and `hi`.
4
Step 4: Iterate through the rest of the array (from index `k` to `nums.length - 1`).
5
Step 5: For each iteration, remove the element that's leaving the window (`out_num`) and add the new element that's entering the window (`in_num`). Update the `to_remove` map with the `out_num`.
6
Step 6: Based on whether `out_num` and `in_num` should belong to the `lo` or `hi` heap, update the heap and calculate the `balance` (difference in sizes) after each operation
7
Step 7: Rebalance the heaps to maintain the property that `lo` has either the same number of elements as `hi` (if `k` is even) or one more (if `k` is odd).
8
Step 8: Clean the heap's tops by removing delayed deletions, ensuring that any delayed deletions present at the top are cleared from both heaps. Delayed deletions are maintained within a hashmap.
9
Step 9: Calculate the median of the current window as in step 3 and add it to the result.
10
Step 10: Repeat steps 5-9 until the end of the `nums` array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log k)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(k)

📝

Why?

The time complexity is dominated by the heap operations. Each `heapq.heappush` and `heapq.heappop` operation takes O(log k) time. We perform these operations for each of the n-k+1 windows in the main loop. The space complexity comes from storing elements in the heaps and the to_remove map, which are both bounded by the size of the sliding window, k.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a sorted list

Maintain a sorted list of the elements in the window. Each time the window slides, remove the outgoing element and add the incoming element, maintaining the sorted order. Find the median from the sorted list.

Time: O(n * k) in the worst case and O(n*logk) with a balanced tree.Space: O(k)

Trade-offs: This approach is conceptually simpler, but less efficient than the two-heap approach. Adding/removing elements can take O(k) in worst cases due to potential shifting needed to maintain a sorted array, leading to an O(nk) time complexity. Using a balanced search tree would allow O(log k) insert and delete leading to O(n log k), however the heap approach is generally more performant in practice due to lower constant factors.

Multiset (C++)

C++ `std::multiset` can be used to efficiently store and retrieve the median. Removing old and adding new values take O(log k) time. Finding iterator takes O(k).

Time: O(n log k)Space: O(k)

Trade-offs: Better than naive sorted list approach, comparable to the Heap solution, but language-specific.

✨

Key Insights

1Insight 1: Using two heaps (a min-heap and a max-heap) allows efficient tracking of the window's elements and finding the median without sorting the window in each step.
2Insight 2: A crucial optimization is to use a `to_remove` map to handle elements that are no longer in the sliding window. This avoids directly removing elements from the heaps, which would be an O(k) operation, significantly improving performance.
3Insight 3: Balancing the heaps to maintain the median efficiently is crucial. The max-heap stores the smaller half of the elements, and the min-heap stores the larger half. Maintaining this balance after each window slide is essential for O(1) median retrieval.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

Edge Cases

Edge case 1: `k` is 1: The median is just the value of the current element. The code handles this case correctly, as the heaps will contain only one element (or potentially be empty after removals).
Edge case 2: `nums` contains duplicate elements: The code handles duplicates correctly because the heaps and the `to_remove` map allow for multiple instances of the same value. The heap balancing logic remains valid regardless of the presence of duplicates.
Edge case 3: When an element to be removed is the current maximum or minimum of a heap: The `to_remove` map and the heap cleaning loops ensure that these elements are properly removed from consideration when they reach the top of the heap.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to rebalance the heaps after adding and removing elements can lead to incorrect median values.

✗Common mistake 2: Directly removing elements from the middle of the heaps is inefficient, as it requires heapifying, which takes O(k) time. Using a `to_remove` map and only removing elements from the top of the heaps is a more efficient approach.

✗Common mistake 3: Incorrectly handling the case where `k` is even or odd. The median calculation is different in these two cases.

✗Common mistake 4: Forgetting to clean the heaps of delayed deletions can lead to outdated elements influencing the calculation of the median.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Tracking the median value of real-time stock prices over a rolling time window to detect trends or anomalies.

🏦Real-world scenario 2: Monitoring the median CPU utilization of a server cluster over a sliding window to identify potential overload situations or capacity planning needs.

🎮Real-world scenario 3: In signal processing, calculating the median of a sliding window to smooth noisy data while preserving edges.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 29, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterMay 30

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Sliding Window Median"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?