Maximum Sliding Window Median

📋

Maximum Sliding Window Median

Edge cases:

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [1,3,3,3,5,6]Incorrect median calculation by picking max or min instead of median in two heaps.✅ Balance heaps after each insertion/removal and compute median from tops of heaps.

Wrong: [2,4,4,4]Incorrect median for even k by returning one middle element instead of average of two middles.✅ For even k, median = (max of lower heap + min of upper heap) / 2.

Wrong: [5]Fails to handle k=1 by overcomplicating or returning empty result.✅ Return each element as median when k=1 without complex data structures.

Wrong: [7,7,6]Incorrect handling of duplicates causing premature removal or wrong median.✅ Use lazy removal with counts or indices to remove only the correct element.

Wrong: TLE or timeoutBrute force sorting each window causing O(n*k log k) time complexity.✅ Implement two heaps with lazy removal for O(n log k) complexity.

✓

Test Cases

Focus on handling small and boundary inputs correctly before tackling edge cases.

Understand the pitfalls of greedy and duplicate handling to solve corner cases.

Optimize your solution to O(n log k) using two heaps with lazy removal 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

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.

💡 Consider 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 find medians efficiently.

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

Why it failed: Failed basic case t1_01: likely incorrect median calculation or window sliding logic. Fix by correctly balancing two heaps and removing elements lazily.

✓ Correctly computes medians for sliding windows using two heaps.

t1_02basic

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

Expected[2.5,3.5,3,3.5]

⏱ Performance - must finish in 2000ms

Sliding windows: [2,1,4,7], [1,4,7,2], [4,7,2,0], [7,2,0,5]. Medians: 2.5, 3.5, 3, 3.5 respectively.

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

💡 Maintain balanced heaps and update median after each slide.

💡 Ensure to remove the element exiting the window from the correct heap.

Why it failed: Failed basic case t1_02: median calculation for even window size incorrect or element removal buggy. Fix by averaging two middle values and lazy removal.

✓ Handles even-sized windows and updates medians correctly.

t2_01edge

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

Expected[5]

⏱ Performance - must finish in 2000ms

Window size 1 means median is the element itself.

💡 When k=1, median is always the single element in the window.

💡 No need for complex data structures for k=1.

💡 Return the original array as medians directly.

Why it failed: Failed edge case t2_01: code does not handle k=1 correctly, possibly overcomplicating. Fix by returning each element as median when k=1.

✓ Correctly returns each element as median for k=1.

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.

💡 Check if your code handles duplicates correctly in heaps.

💡 Ensure lazy removal does not remove all duplicates prematurely.

💡 Median should be the repeated element regardless of window position.

Why it failed: Failed edge case t2_02: duplicates mishandled causing wrong median. Fix by tracking counts and lazy removals properly.

✓ Handles duplicates correctly and returns consistent medians.

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.

💡 When k equals nums.length, only one median to compute.

💡 Sort entire array or use heaps to find median once.

💡 Median is middle element for odd length arrays.

Why it failed: Failed edge case t2_03: code does not handle full-length window correctly. Fix by computing median once for entire array.

✓ Correctly computes median for full-length window.

t2_04edge

Input{"nums":[-1,0,1],"k":2}

Expected[-0.5,0.5]

⏱ Performance - must finish in 2000ms

Window size 2 with negative and positive numbers; median is average of two middle elements.

💡 Median for even k is average of two middle elements.

💡 Heaps must handle negative and positive values correctly.

💡 Balance heaps and compute median as usual.

Why it failed: Failed edge case t2_04: sign handling bug causes wrong median. Fix by using data structures that support negative values.

✓ Correctly computes median with mixed sign numbers.

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 for even k with increasing sequence, catching greedy approach errors.

💡 Greedy approach picking local min or max fails here.

💡 Use balanced heaps to maintain correct median over sliding window.

💡 Balance heaps after each insertion/removal to get correct median.

Why it failed: Failed corner case t3_01: greedy approach returns wrong median. Fix by using two heaps and balancing after each update.

✓ Correctly handles sliding median 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 handling of multiple identical elements with sliding window.

💡 Ensure lazy removal does not remove all duplicates incorrectly.

💡 Track counts or indices to remove only the correct element.

💡 Median should remain stable with duplicates.

Why it failed: Failed corner case t3_02: incorrect removal of duplicates causes wrong median. Fix by tracking element indices for removal.

✓ Correctly handles duplicates with lazy removal.

t3_03corner

Input{"nums":[-5,-10,0,5,10],"k":3}

Expected[-10,0,5]

⏱ Performance - must finish in 2000ms

Tests handling of negative and positive numbers mixed in sliding window.

💡 Heaps must handle negative and positive values correctly.

💡 Median calculation must not assume only positive numbers.

💡 Balance heaps and compute median as usual.

Why it failed: Failed corner case t3_03: sign handling bug causes wrong median. Fix by using data structures that support negative values.

✓ Correctly computes median with mixed sign numbers.

t4_01performance

Input{"nums":[9999999,9999998,9999997,9999996,9999995,9999994,9999993,9999992,9999991,9999990,9999989,9999988,9999987,9999986,9999985,9999984,9999983,9999982,9999981,9999980,9999979,9999978,9999977,9999976,9999975,9999974,9999973,9999972,9999971,9999970,9999969,9999968,9999967,9999966,9999965,9999964,9999963,9999962,9999961,9999960,9999959,9999958,9999957,9999956,9999955,9999954,9999953,9999952,9999951,9999950,9999949,9999948,9999947,9999946,9999945,9999944,9999943,9999942,9999941,9999940,9999939,9999938,9999937,9999936,9999935,9999934,9999933,9999932,9999931,9999930,9999929,9999928,9999927,9999926,9999925,9999924,9999923,9999922,9999921,9999920,9999919,9999918,9999917,9999916,9999915,9999914,9999913,9999912,9999911,9999910,9999909,9999908,9999907,9999906,9999905,9999904,9999903,9999902,9999901,9999900],"k":100}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and k=100 to test O(n log k) complexity within 2 seconds.

💡 Brute force sorting each window is too slow (O(n*k log k)).

💡 Use balanced two heaps with lazy removal for O(n log k) performance.

💡 Avoid full sorting; maintain heaps and balance after each slide.

Why it failed: TLE on performance test t4_01: likely using brute force sorting each window. Fix by implementing two heaps with lazy removal for O(n log k) complexity.

✓ Efficient O(n log k) solution passes performance test.

Practice

1. What is the time complexity of the optimized two-heaps solution for the IPO problem with n projects and K selections?

medium

A. O(n log n + K log n) due to sorting and heap operations

B. O(n * K) because each project is processed K times

C. O(n^2) because of nested loops over projects

D. O(n + K) since heaps provide constant time operations

Solution

1. Step 1: Analyze heap insertions and removals

   Building min-heap from n projects costs O(n), sorting implicitly done by heap push. Each project pushed and popped at most once -> O(n log n).

2. Step 2: Analyze K iterations

   Each iteration may pop from min-heap and push to max-heap, plus pop max profit -> O(K log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Combining heap operations yields O(n log n + K log n) [OK]

Hint: Heap operations dominate complexity, not naive loops [OK]

Common Mistakes:

• Assuming O(n*K) due to nested loops
• Ignoring log n factor in heap operations
• Confusing sorting cost with linear cost

2. What is the time complexity of the optimal max-heap based algorithm for minimizing deviation in an array of size n with maximum element M?

medium

A. O(n^2)

B. O(n log M)

C. O(n log n)

D. O(n log n * log M)

Solution

1. Step 1: Analyze heap operations per element

   Each element is pushed once initially, O(n log n). Then max elements are halved repeatedly, up to log M times.

2. Step 2: Combine heap operations and halving steps

   Each halving involves a pop and push on heap, each O(log n), repeated up to log M times per element, total O(n log n * log M).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Complexity accounts for heap operations and repeated halving [OK]

Hint: Repeated halving causes extra log M factor multiplied by heap ops [OK]

Common Mistakes:

• Ignoring the log M factor from repeated halving
• Confusing n log n with n log M
• Assuming quadratic complexity due to nested loops

3. Consider the following buggy code snippet for the two heaps approach to find next intervals. Which line contains the subtle bug that causes incorrect results on some inputs?

import heapq

def find_next_intervals(intervals):
    n = len(intervals)
    result = [-1] * n
    max_start_heap = []
    max_end_heap = []

    for i, (start, end) in enumerate(intervals):
        heapq.heappush(max_start_heap, (start, i))  # Line 9
        heapq.heappush(max_end_heap, (-end, i))

    while max_end_heap:
        end, end_idx = heapq.heappop(max_end_heap)
        end = -end

        if not max_start_heap or -max_start_heap[0][0] < end:
            continue

        candidates = []
        while max_start_heap and -max_start_heap[0][0] >= end:
            start, start_idx = heapq.heappop(max_start_heap)
            candidates.append((start, start_idx))

        min_start, min_idx = max(candidates)
        result[end_idx] = min_idx

        for c in candidates:
            if c != (min_start, min_idx):
                heapq.heappush(max_start_heap, c)

    return result

medium

A. Line 12: Pushing intervals into max_end_heap with negative end times.

B. Line 9: Using a min-heap push with (start, i) instead of max-heap with (-start, i).

C. Line 18: Checking if max_start_heap is empty or top start < end incorrectly.

D. Line 26: Pushing back unused candidates into max_start_heap.

Solution

1. Step 1: Identify heap usage

   max_start_heap must be a max-heap by pushing (-start, i) to pop intervals with largest start first.

2. Step 2: Analyze Line 9

   Line 9 pushes (start, i) without negation, making it a min-heap, breaking the logic that relies on max-heap ordering.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using min-heap here causes incorrect candidate selection [OK]

Hint: Max-heap requires negation; missing negation breaks logic [OK]

Common Mistakes:

• Forgetting to negate start for max-heap
• Misusing min-heap for max-heap logic
• Incorrect candidate selection due to heap order

4. Suppose employees can have overlapping intervals that are not sorted within their schedules, and intervals can be reused or repeated. Which modification to the optimal approach is necessary to correctly find employee free time?

hard

A. Use a min-heap to merge intervals from each employee's schedule without flattening all intervals at once.

B. Sort intervals within each employee before flattening, then flatten and merge all intervals as usual.

C. Flatten all intervals without sorting, then merge overlapping intervals in a single pass.

D. Ignore repeated intervals since they do not affect free time calculation.

Solution

1. Step 1: Understand problem variant

   Intervals within employees are unsorted and may repeat, so flattening without sorting leads to incorrect merges.

2. Step 2: Evaluate approaches

   Sorting each employee's intervals then flattening (A) is costly and may not handle repeats efficiently. Flattening without sorting (C) breaks merging logic. Ignoring repeats (D) risks missing overlaps. Using a min-heap to merge sorted intervals from each employee (B) handles unsorted input and duplicates correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap merging handles unsorted and repeated intervals efficiently [OK]

Hint: Min-heap merging handles unsorted, repeated intervals [OK]

Common Mistakes:

• Flattening without sorting
• Ignoring duplicates
• Sorting all intervals repeatedly

5. Suppose the problem is modified so that characters can be reused unlimited times (infinite supply), but still must be placed at least k distance apart. Which modification to the original algorithm is necessary to handle this variant correctly?

hard

A. Remove the frequency counter and always push characters back into the heap after cooldown

B. Use a backtracking approach because greedy fails when characters can be reused infinitely

C. Switch to a simple round-robin scheduling without a heap since frequency is irrelevant

D. Use a max heap and cooldown queue as before, but do not decrement counts since supply is infinite

Solution

1. Step 1: Understand infinite supply impact

   Since supply is infinite, counts do not decrease, but k-distance constraint remains.

2. Step 2: Modify algorithm accordingly

   Keep max heap and cooldown queue to enforce spacing, but do not decrement counts; always push characters back after cooldown.

3. Step 3: Why other options fail

   Removing frequency counter loses ordering; round-robin ignores frequency priority; backtracking is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Cooldown queue enforces spacing, heap maintains priority [OK]

Hint: Infinite supply means no decrement, but cooldown still needed [OK]

Common Mistakes:

• Removing heap and losing priority order
• Trying backtracking unnecessarily
• Ignoring cooldown queue and violating k-distance