Sliding Window Median

🎯

Sliding Window Median

hardHEAPAmazonGoogle

Imagine monitoring the median temperature over the last hour, updating every minute as new data arrives and old data expires.

💡 This problem requires maintaining a median over a moving window, which is tricky because the window changes dynamically. Beginners often struggle with efficiently updating medians when elements leave and enter the window.

📋

Problem Statement

Given an integer array nums and a sliding window size k, return an array of the medians of each sliding window of size k moving from left to right across nums. The median is the middle value in an ordered integer list. If the size of the list is even, the median is the average of the two middle values.

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]

Sliding windows and their medians: [1,3,-1] → 1, [3,-1,-3] → -1, [-1,-3,5] → -1, [-3,5,3] → 3, [5,3,6] → 5, [3,6,7] → 6

• k = 1 → median is each element itself
• All elements are the same → median equals that element
• Window size equals array length → median of entire array
• Negative and positive numbers mixed → median calculation correctness

⚠️

Common Mistakes

Removing elements directly from heaps without lazy deletion

Heap structure breaks or removal is O(n), causing TLE

✅ Implement lazy deletion with a hash map to mark removals

Not balancing heaps after insertions and deletions

Median calculation becomes incorrect due to size imbalance

✅ Always rebalance heaps so size difference is at most one

Incorrect median calculation for even window sizes

Wrong median values returned, failing tests

✅ Return average of two middle elements for even k

Using sorting for each window in large inputs

Solution times out due to O(n k log k) complexity

✅ Use two heaps or balanced BST to achieve O(n log k)

Forgetting to prune heaps after lazy deletion

Heaps contain stale elements, causing incorrect median

✅ Prune heaps by removing delayed elements from top after each operation

🧠

Brute Force (Sort Each Window)

💡 This approach is the most straightforward: for each window, sort the elements and find the median. It helps beginners understand the problem mechanics before optimizing.

Intuition

For each sliding window, extract the elements, sort them, and pick the median. Repeat for all windows.

Algorithm

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

💡 The main difficulty is realizing that sorting every window is expensive and redundant, but it clarifies what median means in this context.

</>

Code

from typing import List

def medianSlidingWindow(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()
        mid = k // 2
        if k % 2 == 1:
            median = float(window[mid])
        else:
            median = (window[mid - 1] + window[mid]) / 2
        result.append(median)
    return result

# Example usage
if __name__ == '__main__':
    print(medianSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

for i in range(n - k + 1):Iterate over all valid window start indices

window = nums[i:i+k]Extract the current window elements

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

if k % 2 == 1:Check if window size is odd to pick middle element

median = float(window[mid])Median is the middle element for odd-sized window

median = (window[mid - 1] + window[mid]) / 2Median is average of two middle elements for even-sized window

result.append(median)Add the median to the output list

import java.util.*;

public class SlidingWindowMedian {
    public static double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] result = new double[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int[] window = Arrays.copyOfRange(nums, i, i + k);
            Arrays.sort(window);
            int mid = k / 2;
            if (k % 2 == 1) {
                result[i] = (double) window[mid];
            } else {
                result[i] = ((double) window[mid - 1] + window[mid]) / 2.0;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        double[] medians = medianSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(medians));
    }
}

Line Notes

for (int i = 0; i <= n - k; i++) {Loop over all windows

int[] window = Arrays.copyOfRange(nums, i, i + k);Copy current window elements

Arrays.sort(window);Sort window to find median

if (k % 2 == 1) {Check odd window size

result[i] = (double) window[mid];Median is middle element for odd k

result[i] = ((double) window[mid - 1] + window[mid]) / 2.0;Median is average for even k

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

using namespace std;

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<double> result;
    for (int i = 0; i <= n - k; i++) {
        vector<int> window(nums.begin() + i, nums.begin() + i + k);
        sort(window.begin(), window.end());
        int mid = k / 2;
        if (k % 2 == 1) {
            result.push_back((double)window[mid]);
        } else {
            result.push_back(((double)window[mid - 1] + window[mid]) / 2.0);
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    vector<double> medians = medianSlidingWindow(nums, 3);
    for (double m : medians) cout << m << " ";
    cout << endl;
    return 0;
}

Line Notes

for (int i = 0; i <= n - k; i++) {Iterate over all sliding windows

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

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

if (k % 2 == 1) {Check if window size is odd

result.push_back((double)window[mid]);Median is middle element for odd k

result.push_back(((double)window[mid - 1] + window[mid]) / 2.0);Median is average for even k

function medianSlidingWindow(nums, k) {
    const n = nums.length;
    const result = [];
    for (let i = 0; i <= n - k; i++) {
        const window = nums.slice(i, i + k);
        window.sort((a, b) => a - b);
        const mid = Math.floor(k / 2);
        if (k % 2 === 1) {
            result.push(window[mid]);
        } else {
            result.push((window[mid - 1] + window[mid]) / 2);
        }
    }
    return result;
}

// Example usage
console.log(medianSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

for (let i = 0; i <= n - k; i++) {Loop over all windows

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

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

if (k % 2 === 1) {Check odd window size

result.push(window[mid]);Median is middle element for odd k

result.push((window[mid - 1] + window[mid]) / 2);Median is average for even k

⏱

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.

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

Interview Verdict: TLE for large inputs

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

🧠

Balanced Two Heaps with Lazy Deletion

💡 This approach uses two heaps to maintain the lower and upper halves of the window, allowing median retrieval in O(1) and updates in O(log k). Lazy deletion handles removals efficiently.

Intuition

Maintain two heaps: a max-heap for the smaller half and a min-heap for the larger half of the current window. Balance their sizes so median is accessible from the tops.

Algorithm

1. Initialize two heaps: max-heap for smaller half, min-heap for larger half.
2. Insert first k elements, balancing heaps after each insertion.
3. For each window, the median is either the top of max-heap or average of tops if even-sized.
4. When sliding the window, remove the outgoing element lazily and add the incoming element, rebalancing heaps.

💡 The challenge is managing removals efficiently without direct heap element deletion, solved by lazy deletion with a hash map.

</>

Code

import heapq
from collections import defaultdict
from typing import List

class DualHeap:
    def __init__(self, k):
        self.small = []  # max heap (invert values)
        self.large = []  # min heap
        self.delayed = defaultdict(int)  # counts of elements to remove
        self.k = k
        self.small_size = 0
        self.large_size = 0

    def prune(self, heap):
        while heap and self.delayed[heap[0][1]] > 0:
            num = heap[0][1]
            self.delayed[num] -= 1
            if self.delayed[num] == 0:
                del self.delayed[num]
            heapq.heappop(heap)

    def balance(self):
        if self.small_size > self.large_size + 1:
            val = heapq.heappop(self.small)[1]
            heapq.heappush(self.large, (val, val))
            self.small_size -= 1
            self.large_size += 1
            self.prune(self.small)
        elif self.small_size < self.large_size:
            val = heapq.heappop(self.large)[1]
            heapq.heappush(self.small, (-val, val))
            self.large_size -= 1
            self.small_size += 1
            self.prune(self.large)

    def insert(self, num):
        if not self.small or num <= self.small[0][1]:
            heapq.heappush(self.small, (-num, num))
            self.small_size += 1
        else:
            heapq.heappush(self.large, (num, num))
            self.large_size += 1
        self.balance()

    def erase(self, num):
        self.delayed[num] += 1
        if num <= self.small[0][1]:
            self.small_size -= 1
            if num == self.small[0][1]:
                self.prune(self.small)
        else:
            self.large_size -= 1
            if self.large and num == self.large[0][1]:
                self.prune(self.large)
        self.balance()

    def get_median(self):
        if self.k % 2 == 1:
            return float(self.small[0][1])
        else:
            return (self.small[0][1] + self.large[0][1]) / 2


def medianSlidingWindow(nums: List[int], k: int) -> List[float]:
    dh = DualHeap(k)
    for i in range(k):
        dh.insert(nums[i])
    result = [dh.get_median()]
    for i in range(k, len(nums)):
        dh.insert(nums[i])
        dh.erase(nums[i - k])
        result.append(dh.get_median())
    return result

# Example usage
if __name__ == '__main__':
    print(medianSlidingWindow([1,3,-1,-3,5,3,6,7], 3))

Line Notes

self.small = [] # max heap (invert values)Use negative values to simulate max heap in Python

self.delayed = defaultdict(int)Track elements to lazily remove from heaps

def prune(self, heap):Remove elements marked for deletion from heap top

def balance(self):Ensure heaps sizes differ by at most one

def insert(self, num):Add new number to appropriate heap and rebalance

def erase(self, num):Mark number for lazy deletion and rebalance

def get_median(self):Return median based on heap sizes and tops

import java.util.*;

public class SlidingWindowMedian {
    class DualHeap {
        PriorityQueue<Integer> small, large;
        Map<Integer, Integer> delayed;
        int k, smallSize, largeSize;

        public DualHeap(int k) {
            this.k = k;
            small = new PriorityQueue<>(Collections.reverseOrder());
            large = new PriorityQueue<>();
            delayed = new HashMap<>();
            smallSize = 0;
            largeSize = 0;
        }

        private void prune(PriorityQueue<Integer> heap) {
            while (!heap.isEmpty()) {
                int num = heap.peek();
                if (delayed.containsKey(num)) {
                    delayed.put(num, delayed.get(num) - 1);
                    if (delayed.get(num) == 0) delayed.remove(num);
                    heap.poll();
                } else {
                    break;
                }
            }
        }

        private void balance() {
            if (smallSize > largeSize + 1) {
                int val = small.poll();
                large.offer(val);
                smallSize--;
                largeSize++;
                prune(small);
            } else if (smallSize < largeSize) {
                int val = large.poll();
                small.offer(val);
                largeSize--;
                smallSize++;
                prune(large);
            }
        }

        public void insert(int num) {
            if (small.isEmpty() || num <= small.peek()) {
                small.offer(num);
                smallSize++;
            } else {
                large.offer(num);
                largeSize++;
            }
            balance();
        }

        public void erase(int num) {
            delayed.put(num, delayed.getOrDefault(num, 0) + 1);
            if (!small.isEmpty() && num <= small.peek()) {
                smallSize--;
                if (num == small.peek()) prune(small);
            } else {
                largeSize--;
                if (!large.isEmpty() && num == large.peek()) prune(large);
            }
            balance();
        }

        public double getMedian() {
            if (k % 2 == 1) return (double) small.peek();
            else return ((double) small.peek() + large.peek()) / 2.0;
        }
    }

    public static double[] medianSlidingWindow(int[] nums, int k) {
        SlidingWindowMedian swm = new SlidingWindowMedian();
        DualHeap dh = swm.new DualHeap(k);
        for (int i = 0; i < k; i++) dh.insert(nums[i]);
        double[] result = new double[nums.length - k + 1];
        result[0] = dh.getMedian();
        for (int i = k; i < nums.length; i++) {
            dh.insert(nums[i]);
            dh.erase(nums[i - k]);
            result[i - k + 1] = dh.getMedian();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        double[] medians = medianSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(medians));
    }
}

Line Notes

small = new PriorityQueue<>(Collections.reverseOrder());Max heap for smaller half

delayed = new HashMap<>();Map to track lazy deletions

private void prune(PriorityQueue<Integer> heap) {Remove elements marked for deletion from heap top

private void balance() {Balance heaps sizes to maintain median property

public void insert(int num) {Insert new element into correct heap

public void erase(int num) {Mark element for lazy deletion and rebalance

public double getMedian() {Return median from heap tops

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class DualHeap {
    priority_queue<int> small; // max heap
    priority_queue<int, vector<int>, greater<int>> large; // min heap
    unordered_map<int, int> delayed;
    int k, smallSize, largeSize;

    void prune(priority_queue<int>& heap) {
        while (!heap.empty()) {
            int num = heap.top();
            if (delayed.count(num)) {
                delayed[num]--;
                if (delayed[num] == 0) delayed.erase(num);
                heap.pop();
            } else break;
        }
    }

    void prune(priority_queue<int, vector<int>, greater<int>>& heap) {
        while (!heap.empty()) {
            int num = heap.top();
            if (delayed.count(num)) {
                delayed[num]--;
                if (delayed[num] == 0) delayed.erase(num);
                heap.pop();
            } else break;
        }
    }

    void balance() {
        if (smallSize > largeSize + 1) {
            int val = small.top(); small.pop();
            large.push(val);
            smallSize--;
            largeSize++;
            prune(small);
        } else if (smallSize < largeSize) {
            int val = large.top(); large.pop();
            small.push(val);
            largeSize--;
            smallSize++;
            prune(large);
        }
    }

public:
    DualHeap(int k): k(k), smallSize(0), largeSize(0) {}

    void insert(int num) {
        if (small.empty() || num <= small.top()) {
            small.push(num);
            smallSize++;
        } else {
            large.push(num);
            largeSize++;
        }
        balance();
    }

    void erase(int num) {
        delayed[num]++;
        if (!small.empty() && num <= small.top()) {
            smallSize--;
            if (num == small.top()) prune(small);
        } else {
            largeSize--;
            if (!large.empty() && num == large.top()) prune(large);
        }
        balance();
    }

    double getMedian() {
        if (k % 2 == 1) return (double)small.top();
        else return ((double)small.top() + large.top()) / 2.0;
    }
};

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    DualHeap dh(k);
    for (int i = 0; i < k; i++) dh.insert(nums[i]);
    vector<double> result = {dh.getMedian()};
    for (int i = k; i < (int)nums.size(); i++) {
        dh.insert(nums[i]);
        dh.erase(nums[i - k]);
        result.push_back(dh.getMedian());
    }
    return result;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    vector<double> medians = medianSlidingWindow(nums, 3);
    for (double m : medians) cout << m << " ";
    cout << endl;
    return 0;
}

Line Notes

priority_queue<int> small;Max heap for smaller half

unordered_map<int, int> delayed;Track lazy deletions

void prune(priority_queue<int>& heap) {Remove delayed elements from max heap

void prune(priority_queue<int, vector<int>, greater<int>>& heap) {Remove delayed elements from min heap

void balance() {Balance heap sizes to maintain median property

void insert(int num) {Insert element into correct heap

void erase(int num) {Mark element for lazy deletion and rebalance

double getMedian() {Return median from heap tops

class DualHeap {
    constructor(k) {
        this.small = new MaxHeap();
        this.large = new MinHeap();
        this.delayed = new Map();
        this.k = k;
        this.smallSize = 0;
        this.largeSize = 0;
    }

    prune(heap) {
        while (!heap.isEmpty()) {
            let num = heap.peek();
            if (this.delayed.has(num)) {
                this.delayed.set(num, this.delayed.get(num) - 1);
                if (this.delayed.get(num) === 0) this.delayed.delete(num);
                heap.pop();
            } else break;
        }
    }

    balance() {
        if (this.smallSize > this.largeSize + 1) {
            let val = this.small.pop();
            this.large.push(val);
            this.smallSize--;
            this.largeSize++;
            this.prune(this.small);
        } else if (this.smallSize < this.largeSize) {
            let val = this.large.pop();
            this.small.push(val);
            this.largeSize--;
            this.smallSize++;
            this.prune(this.large);
        }
    }

    insert(num) {
        if (this.small.isEmpty() || num <= this.small.peek()) {
            this.small.push(num);
            this.smallSize++;
        } else {
            this.large.push(num);
            this.largeSize++;
        }
        this.balance();
    }

    erase(num) {
        this.delayed.set(num, (this.delayed.get(num) || 0) + 1);
        if (!this.small.isEmpty() && num <= this.small.peek()) {
            this.smallSize--;
            if (num === this.small.peek()) this.prune(this.small);
        } else {
            this.largeSize--;
            if (!this.large.isEmpty() && num === this.large.peek()) this.prune(this.large);
        }
        this.balance();
    }

    getMedian() {
        if (this.k % 2 === 1) return this.small.peek();
        else return (this.small.peek() + this.large.peek()) / 2;
    }
}

// Simple heap implementations omitted for brevity; assume MaxHeap and MinHeap classes exist with push, pop, peek, isEmpty

function medianSlidingWindow(nums, k) {
    const dh = new DualHeap(k);
    for (let i = 0; i < k; i++) dh.insert(nums[i]);
    const result = [dh.getMedian()];
    for (let i = k; i < nums.length; i++) {
        dh.insert(nums[i]);
        dh.erase(nums[i - k]);
        result.push(dh.getMedian());
    }
    return result;
}

// Example usage
console.log(medianSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

Line Notes

this.small = new MaxHeap();Max heap for smaller half

this.delayed = new Map();Map to track lazy deletions

prune(heap) {Remove elements marked for deletion from heap top

balance() {Balance heaps sizes to maintain median property

insert(num) {Insert new number into correct heap

erase(num) {Mark number for lazy deletion and rebalance

getMedian() {Return median from heap tops

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Each insertion and lazy deletion costs O(log k), done n times, total O(n log k).

💡 For n=100000 and k=1000, this is about 100000 * 10 = 1,000,000 operations, efficient enough for interviews.

Interview Verdict: Accepted

This is the standard optimal approach for sliding window median problems in interviews.

🧠

Balanced Two Heaps with TreeMap / Balanced BST (Java Specific)

💡 Instead of heaps, use a balanced BST (TreeMap) to maintain counts and order, allowing O(log k) insertion, deletion, and median retrieval by tracking counts.

Intuition

Use a TreeMap to store counts of elements in the window, and maintain pointers to median elements by counting ranks.

Algorithm

1. Use two TreeMaps to represent lower and upper halves with counts.
2. Insert first k elements, balancing counts.
3. For each window, median is top of lower half or average of tops.
4. Remove outgoing element and add incoming element, rebalancing counts.

💡 This approach is more complex but avoids lazy deletion and is easier in languages with built-in balanced trees.

</>

Code

# This approach is Java-specific due to TreeMap; omitted in Python

Line Notes

N/ATreeMap not available in Python standard library

import java.util.*;

public class SlidingWindowMedian {
    TreeMap<Integer, Integer> lo = new TreeMap<>(Collections.reverseOrder());
    TreeMap<Integer, Integer> hi = new TreeMap<>();
    int loSize = 0, hiSize = 0;
    int k;

    public SlidingWindowMedian(int k) {
        this.k = k;
    }

    private void add(TreeMap<Integer, Integer> map, int num) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    private void remove(TreeMap<Integer, Integer> map, int num) {
        int count = map.get(num);
        if (count == 1) map.remove(num);
        else map.put(num, count - 1);
    }

    private void balance() {
        while (loSize > hiSize + 1) {
            int maxLo = lo.firstKey();
            remove(lo, maxLo);
            loSize--;
            add(hi, maxLo);
            hiSize++;
        }
        while (loSize < hiSize) {
            int minHi = hi.firstKey();
            remove(hi, minHi);
            hiSize--;
            add(lo, minHi);
            loSize++;
        }
    }

    private void insert(int num) {
        if (lo.isEmpty() || num <= lo.firstKey()) {
            add(lo, num);
            loSize++;
        } else {
            add(hi, num);
            hiSize++;
        }
        balance();
    }

    private void erase(int num) {
        if (lo.containsKey(num) && num <= lo.firstKey()) {
            remove(lo, num);
            loSize--;
        } else {
            remove(hi, num);
            hiSize--;
        }
        balance();
    }

    private double getMedian() {
        if (k % 2 == 1) return (double) lo.firstKey();
        else return ((double) lo.firstKey() + hi.firstKey()) / 2.0;
    }

    public double[] medianSlidingWindow(int[] nums) {
        int n = nums.length;
        double[] result = new double[n - k + 1];
        for (int i = 0; i < k; i++) insert(nums[i]);
        result[0] = getMedian();
        for (int i = k; i < n; i++) {
            insert(nums[i]);
            erase(nums[i - k]);
            result[i - k + 1] = getMedian();
        }
        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMedian swm = new SlidingWindowMedian(3);
        int[] nums = {1,3,-1,-3,5,3,6,7};
        double[] medians = swm.medianSlidingWindow(nums);
        System.out.println(Arrays.toString(medians));
    }
}

Line Notes

TreeMap<Integer, Integer> lo = new TreeMap<>(Collections.reverseOrder());Max ordered map for lower half

TreeMap<Integer, Integer> hi = new TreeMap<>();Min ordered map for upper half

private void add(TreeMap<Integer, Integer> map, int num) {Add element count to map

private void remove(TreeMap<Integer, Integer> map, int num) {Remove or decrement element count

private void balance() {Balance sizes of two maps

private void insert(int num) {Insert element into correct map

private void erase(int num) {Remove element from correct map

private double getMedian() {Calculate median from map keys

// This approach is Java-specific due to TreeMap; omitted in C++

Line Notes

N/ANo direct TreeMap equivalent in C++ STL

// This approach is Java-specific due to TreeMap; omitted in JavaScript

Line Notes

N/ANo direct TreeMap equivalent in JavaScript

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Insertion, deletion, and balancing in TreeMap cost O(log k) each, done n times.

💡 This approach is efficient but more complex to implement than heaps.

Interview Verdict: Accepted (Java only)

Useful in Java interviews where TreeMap is available; less common in other languages.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the two heaps with lazy deletion approach in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sort Each Window)	O(n k log k)	O(k)	No	N/A	Mention only - never code
2. Balanced Two Heaps with Lazy Deletion	O(n log k)	O(k)	No	N/A	Code this approach
3. Balanced Two Heaps with TreeMap (Java only)	O(n log k)	O(k)	No	N/A	Mention if language supports TreeMap

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify problem constraints and median definition.Explain brute force approach and its inefficiency.Introduce two heaps and lazy deletion for optimal solution.Discuss balancing heaps and median retrieval.Mention TreeMap approach if language supports it.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 5min. Total ~27min

What the Interviewer Tests

Ability to handle dynamic data structures, balance heaps, implement lazy deletion, and optimize time complexity.

Common Follow-ups

• What if window size k is 1? → Median is each element itself.
• How to handle duplicates efficiently? → Use lazy deletion or counts.
• Can we do better than O(n log k)? → No known better for median in sliding window.
• How to extend to streaming data? → Use two heaps with lazy deletion.

💡 These follow-ups test understanding of edge cases, duplicates, complexity limits, and real-world streaming scenarios.

🔍

Pattern Recognition

When to Use

1) Need median or order statistic in a sliding window 2) Window size fixed and moves 3) Efficient insert and remove required 4) Median must be updated dynamically

Signature Phrases

sliding window medianmedian of each windowdynamic median updates

NOT This Pattern When

Problems requiring sum or max/min in window without median do not need two heaps.

Similar Problems

Median of Data Stream - similar median maintenance with two heapsFind Median from Data Stream - streaming median problemSliding Window Maximum - similar sliding window with max heap

Practice

1. Given the following Python code implementing the optimal two heaps approach for finding next intervals, what is the final returned result for the input intervals = [(2,3), (3,4), (1,2)]?

easy

A. [2, 0, 1]

B. [0, -1, 1]

C. [-1, -1, -1]

D. [1, -1, 0]

Solution

1. Step 1: Initialize heaps and result

   max_start_heap = [(-3,1), (-2,0), (-1,2)], max_end_heap = [(-4,1), (-3,0), (-2,2)], result = [-1, -1, -1]

2. Step 2: Process max_end_heap

   Pop (-4,1): max_start_heap top is -3 < 4, continue no update.
   Pop (-3,0): max_start_heap top -3 >= 3, pop candidates with start >= 3: (-3,1). min_start= -3, min_idx=1, result[0]=1.
   Push back unused candidates (none).
   Pop (-2,2): max_start_heap top -2 >= 2, pop candidates (-2,0), (-1,2). min_start= -1, min_idx=2, result[2]=2.
   Push back (-2,0).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches expected output for given input [OK]

Hint: Track heap pops carefully to find correct indices [OK]

Common Mistakes:

• Off-by-one in indices
• Not pushing back unused intervals
• Confusing start and end heaps

2. What is the time complexity of the optimal approach that finds employee free time by flattening all intervals, sorting them, and then merging to find gaps?

medium

A. O(N log N) due to sorting all intervals

B. O(N) where N is total number of intervals

C. O(N^2) because merging intervals requires nested comparisons

D. O(N log M) where M is number of employees

Solution

1. Step 1: Identify main operations

   Flattening intervals is O(N). Sorting all intervals by start time is O(N log N).

2. Step 2: Analyze merging step

   Merging intervals in a single pass is O(N). No nested loops for merging.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates complexity, so O(N log N) [OK]

Hint: Sorting all intervals dominates time complexity [OK]

Common Mistakes:

• Assuming linear time due to single pass merge
• Thinking merging is O(N^2)
• Confusing number of employees with intervals count

3. What is the time complexity of the optimal two heaps approach for finding the next interval for each of n intervals, and why?

medium

A. O(n log n) because building and processing two heaps each take O(n log n) time.

B. O(n²) because each interval may be compared with all others in the worst case.

C. O(n) because each interval is pushed and popped from heaps only once.

D. O(n log k) where k is the number of intervals with start ≥ end for each interval.

Solution

1. Step 1: Analyze heap operations

   Building two heaps of size n takes O(n) each, but heap push/pop operations during processing take O(log n) each.

2. Step 2: Count total operations

   Each interval is pushed and popped at most once from each heap, resulting in O(n log n) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap operations dominate complexity, confirming O(n log n) [OK]

Hint: Heap push/pop cost dominates, not linear scans [OK]

Common Mistakes:

• Assuming linear time due to single pass
• Confusing n and k in complexity
• Mistaking nested loops for heap operations

4. The following code attempts to rearrange a string so that the same characters are at least k distance apart. Identify the line containing the subtle bug that can cause invalid output or failure.

medium

A. Line: heapq.heapify(max_heap) # heapify should be replaced with sort

B. Line: if k == 0: return s # should handle k=1 differently

C. Line: queue.append((char, count)) # decrement count missing

D. Line: if front_count < 0: heapq.heappush(max_heap, (front_count, front_char)) # should check for <= 0

Solution

1. Step 1: Identify decrement of count

   The algorithm must decrement the count of the character after using it, i.e., count + 1 since counts are negative.

2. Step 2: Locate missing decrement

   In the buggy line, count is appended without incrementing, so the character count never decreases, causing infinite loops or invalid results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct decrement is critical to track usage [OK]

Hint: Check if character count is updated after usage [OK]

Common Mistakes:

• Forgetting to decrement count after popping from heap
• Misusing queue length to enforce k-distance
• Incorrect heap operations or conditions

5. If the data stream allows removal of arbitrary elements (not just the median), which modification to the balanced two heaps approach is necessary to maintain efficient median retrieval?

hard

A. Implement lazy removal with a delayed dictionary to mark elements for removal and prune heaps lazily.

B. Use a balanced binary search tree instead of heaps for O(log n) insertions and removals.

C. Keep a sorted list and perform binary search for insertions and removals.

D. Rebuild both heaps from scratch after each removal to maintain order.

Solution

1. Step 1: Understand removal challenges

   Removing arbitrary elements from heaps is not efficient since heaps do not support O(log n) arbitrary removals.

2. Step 2: Evaluate solutions

   Rebuilding heaps each removal is O(n log n), too slow. Balanced BST supports removals but is more complex and median retrieval is not O(1). Sorted list has O(n) insertion/removal. Lazy removal uses a delayed dictionary to mark elements for removal and prunes them lazily during heap operations, maintaining O(log n) amortized complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Lazy removal enables efficient arbitrary removals -> [OK]

Hint: Lazy removal with delayed map enables efficient arbitrary removals [OK]

Common Mistakes:

• Rebuilding heaps after each removal is inefficient
• Assuming heaps support O(log n) arbitrary removals directly
• Switching to balanced BST loses O(1) median retrieval