Sliding Window Median

📋

Problem

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

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

Edge cases: k = 1 → median is each element itselfAll elements are the same → median equals that elementWindow size equals array length → median of entire array

</>

IDE

def medianSlidingWindow(nums: list[int], k: int) -> list[float]:public double[] medianSlidingWindow(int[] nums, int k)vector<double> medianSlidingWindow(vector<int>& nums, int k)function medianSlidingWindow(nums, k)

def medianSlidingWindow(nums, k):
    # Write your solution here
    pass

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        // Write your solution here
        return new double[0];
    }
}

#include <vector>
using namespace std;

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    // Write your solution here
    return {};
}

function medianSlidingWindow(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,3,-1,3,5,6]Incorrect median calculation by picking max or min heap top only without averaging for even k.✅ Compute median as average of max of lower heap and min of upper heap when k is even.

Wrong: [5]Fails to handle k=1 by returning the element itself as median.✅ Return each element as median directly when k=1 without heap operations.

Wrong: [7,7,7]Incorrect lazy deletion removes duplicates prematurely causing wrong median.✅ Use a count map to track elements to remove lazily and only remove when count reaches zero.

Wrong: [3,3,7,7,7,7]Off-by-one error in removing outgoing elements from heaps.✅ Ensure correct element is removed from the correct heap and heaps are rebalanced after removal.

Wrong: TLEBrute force sorting each window causing O(n*k log k) time complexity.✅ Implement two heaps with lazy deletion to achieve O(n log k) time complexity.

✓

Test Cases

Focus on handling minimal and maximal window sizes and duplicates correctly.

Watch out for common pitfalls like greedy median selection and lazy deletion bugs.

Optimize your solution to use two heaps with lazy deletion for performance.

t1_01basic

Input{"nums":[1,3,-1,-3,5,3,6,7],"k":3}

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

⏱ Performance - must finish in 2000ms

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

💡 Think about maintaining two heaps to track the lower and upper halves of the window.

💡 Use a max-heap for the lower half and a min-heap for the upper half to get median in O(log k).

💡 Balance heaps after each insertion/removal and compute median from the tops.

Why it failed: Basic case failed - likely incorrect heap balancing or median calculation. Fix by ensuring heaps are balanced so that their sizes differ by at most one and median is computed correctly.

✓ Correct median calculation and heap balancing confirmed.

t1_02basic

Input{"nums":[2,4,6,8,10,12],"k":4}

Expected[5,7,9]

⏱ Performance - must finish in 2000ms

Sliding windows: [2,4,6,8] median is (4+6)/2=5, [4,6,8,10] median is (6+8)/2=7, [6,8,10,12] median is (8+10)/2=9

💡 Remember median for even k is average of two middle elements.

💡 Maintain two heaps and rebalance after sliding the window.

💡 Update heaps by removing outgoing element and adding incoming element carefully.

Why it failed: Median incorrect for even window size - likely missing averaging of two middle elements. Fix by computing median as average of max of lower heap and min of upper heap when k is even.

✓ Handles even window sizes and median averaging correctly.

t2_01edge

Input{"nums":[5],"k":1}

Expected[5]

⏱ Performance - must finish in 2000ms

Window size 1 means median is the element itself.

💡 Check behavior when window size equals 1.

💡 Median should be each element itself without heap balancing.

💡 Return the original array as floats when k=1.

Why it failed: Fails single element window - likely overcomplicating or mishandling k=1. Fix by returning each element as median directly when k=1.

✓ Correctly handles single element windows.

t2_02edge

Input{"nums":[7,7,7,7,7],"k":3}

Expected[7,7,7]

⏱ Performance - must finish in 2000ms

All elements identical, median equals that element for every window.

💡 Test if algorithm handles duplicates correctly.

💡 Ensure lazy deletion or removal logic does not remove all duplicates incorrectly.

💡 Median should remain constant when all elements are the same.

Why it failed: Fails on identical elements - likely incorrect removal or heap balancing causing wrong median. Fix lazy deletion to handle duplicates properly.

✓ Correctly handles windows with all identical elements.

t2_03edge

Input{"nums":[1,2,3,4,5],"k":5}

Expected[3]

⏱ Performance - must finish in 2000ms

Window size equals array length, median is median of entire array.

💡 Check behavior when window size equals array length.

💡 Median is median of whole array, no sliding needed.

💡 Ensure algorithm handles this boundary without errors.

Why it failed: Fails full array window - likely off-by-one or indexing error. Fix by correctly handling window size equal to array length.

✓ Correctly computes median for full array window.

t3_01corner

Input{"nums":[1,2,3,4,5,6,7,8,9],"k":4}

Expected[2.5,3.5,4.5,5.5,6.5,7.5]

⏱ Performance - must finish in 2000ms

Tests correct median calculation for even k with increasing sequence.

💡 Beware of greedy approach that picks median from only one heap.

💡 Check that median is average of two middle elements for even k.

💡 Balance heaps so sizes differ by at most one and compute median accordingly.

Why it failed: Greedy trap: returning top of one heap only for even k. Fix by averaging tops of both heaps when k is even. This is the greedy trap test.

✓ Correctly computes median for even k with balanced heaps.

t3_02corner

Input{"nums":[1,1,1,1,1,1,1],"k":3}

Expected[1,1,1,1,1]

⏱ Performance - must finish in 2000ms

Tests correct lazy deletion handling with duplicates in sliding window.

💡 Check if lazy deletion removes all duplicates incorrectly.

💡 Use a hash map or count to track elements to remove lazily.

💡 Remove elements only when their count reaches zero.

Why it failed: Incorrect lazy deletion removes duplicates prematurely. Fix by tracking counts and removing elements lazily only when count is zero. This is the lazy deletion test.

✓ Correct lazy deletion with duplicates confirmed.

t3_03corner

Input{"nums":[5,2,2,7,3,7,9,0,2,3],"k":5}

Expected[3,3,7,7,7,3]

⏱ Performance - must finish in 2000ms

Tests correct median calculation with mixed negative and positive numbers and duplicates.

💡 Verify correct removal of outgoing elements from heaps.

💡 Ensure heaps are balanced after each slide.

💡 Median must reflect correct middle value after each window slide.

Why it failed: Off-by-one or incorrect removal causes wrong median. Fix by carefully removing outgoing element and rebalancing heaps. This is the off-by-one removal test.

✓ Correct median with mixed values and duplicates confirmed.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with k up to n requires O(n log k) solution to complete within 2 seconds.

💡 Brute force sorting each window is O(n*k log k) and will TLE.

💡 Use two heaps with lazy deletion for O(n log k) time complexity.

💡 Efficiently balance heaps and remove elements lazily to pass performance.

Why it failed: TLE due to brute force or inefficient approach. Fix by implementing two heaps with lazy deletion and balancing for O(n log k) complexity.

✓ Efficient O(n log k) solution confirmed by passing performance test.

Practice

1. You are given a list of projects, each with a required minimum capital to start and a profit earned upon completion. You can start with an initial capital and can select up to K projects sequentially, each time only choosing projects you can afford with your current capital. Which algorithmic approach guarantees finding the maximum possible capital after completing up to K projects?

easy

A. Dynamic programming with a 2D table tracking projects and capital states

B. Brute force recursion exploring all project combinations without pruning

C. Simple sorting of projects by profit and picking the top K projects regardless of capital

D. Greedy approach using two heaps: a min-heap for capital requirements and a max-heap for profits

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting projects affordable at each step, maximizing capital after K picks.

2. Step 2: Identify algorithmic pattern

   Using two heaps allows efficient selection: min-heap to filter affordable projects by capital, max-heap to pick the most profitable among them, ensuring optimal capital gain.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two heaps efficiently handle affordability and profit selection [OK]

Hint: Two heaps handle affordability and profit optimally [OK]

Common Mistakes:

• Assuming sorting by profit alone suffices
• Using brute force without pruning
• Confusing DP with this greedy heap approach

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

3. What is the time complexity of the optimal greedy algorithm that uses a max heap and a fixed-size queue to rearrange a string of length n with m unique characters and distance constraint k?

medium

A. O(n log m) because each character is pushed and popped from a heap of size up to m

B. O(n * k) because each character is processed with a queue of size k

C. O(n^2) because the algorithm may scan the string multiple times to enforce constraints

D. O(m log n) because the heap operations depend on string length n

Solution

1. Step 1: Identify main operations

   Each character is pushed and popped from a max heap of size up to m (number of unique chars), each heap operation costs O(log m).

2. Step 2: Count total operations

   Since total characters are n, total heap operations are O(n), resulting in O(n log m) time complexity. However, the queue operations to enforce the k-distance constraint can cause up to O(n * k) complexity in the worst case because each character waits in the cooldown queue for k steps.

3. Step 3: Choose the tightest upper bound

   Considering the cooldown queue of size k, the overall complexity is O(n * k).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue operations dominate due to cooldown size k [OK]

Hint: Cooldown queue size k affects complexity [OK]

Common Mistakes:

• Ignoring cooldown queue impact
• Assuming heap operations dominate always
• Mixing up m and n in heap operation costs

4. What is the time complexity of the optimized task scheduler algorithm that uses a hash map to track the next available day for each task, given n tasks and cooldown space?

medium

A. O(n * space) due to iterating over cooldown days for each task

B. O(n) because each task is processed once with O(1) hash map operations

C. O(n log n) due to sorting tasks or heap operations

D. O(n^2) because of nested loops checking cooldown constraints

Solution

1. Step 1: Identify operations per task

   Each task is processed once in a single loop over the tasks array.

2. Step 2: Analyze hash map operations

   Hash map lookups and updates for next_available are O(1) on average, so no nested loops or sorting involved.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with O(1) lookups -> O(n) time -> [OK]

Hint: Hash map lookups are O(1), no nested loops -> O(n) [OK]

Common Mistakes:

• Assuming cooldown causes nested loops increasing complexity
• Confusing with heap-based solutions that are O(n log n)
• Thinking space affects time complexity linearly

5. Suppose projects can be selected multiple times (reused) in the IPO problem. Which modification to the two-heaps algorithm correctly handles this scenario?

hard

A. Use a max-heap only and pick the top K profitable projects ignoring capital constraints

B. Do not remove projects from min-capital heap; instead, keep all projects always available

C. After selecting a project, reinsert it into the min-capital heap to allow reuse

D. After selecting a project, do not remove it from max-profit heap to allow repeated selection

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means projects remain available after selection, so they must be reinserted to be considered again.

2. Step 2: Modify algorithm accordingly

   After popping a project from min-capital heap and selecting it, reinsert it to allow future reuse; otherwise, it disappears from consideration.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reinserting projects enables multiple selections [OK]

Hint: Reinsert projects after selection to allow reuse [OK]

Common Mistakes:

• Ignoring reinsertion, losing projects after first pick
• Keeping all projects always available breaks capital filtering
• Ignoring capital constraints when reusing projects