Maximum Sliding Window Median

▶

Steps

setup

Initialize window with first k elements

We start by taking the first k=3 elements [1,3,-1] from nums and sorting them to form the initial window.

💡 Sorting the initial window sets up the data structure to efficiently find medians and prepare for sliding.

Line:

window = sorted(nums[:k])

💡 The initial sorted window represents the balanced data structure holding the first sliding window elements.

compare

Calculate median of initial window

Since k=3 is odd, the median is the middle element of the sorted window, which is 1.

💡 Finding the median from a sorted window is straightforward and confirms the data structure correctness.

Line:

result.append(get_median())

💡 Median is the middle element at index k//2 when window size is odd.

delete

Slide window: remove outgoing element 1

We remove the element nums[0] = 1 from the window by finding its index and popping it.

💡 Removing the outgoing element keeps the window size constant as it slides.

Line:

idx = bisect.bisect_left(window, nums[i - k])
window.pop(idx)

💡 Efficient removal by binary search maintains sorted order without full re-sort.

insert

Slide window: insert incoming element -3

We insert the new element nums[3] = -3 into the window, maintaining sorted order.

💡 Insertion keeps the window balanced and sorted for median calculation.

Line:

bisect.insort_left(window, nums[i])

💡 Insertion via binary search places element correctly without full re-sort.

compare

Calculate median of second window

Median is the middle element of [-3, -1, 3], which is -1.

💡 Median reflects the middle value after sliding the window.

Line:

result.append(get_median())

💡 Median updates as window slides, reflecting new data distribution.

delete

Slide window: remove outgoing element 3

Remove nums[1] = 3 from the window by locating and popping it.

💡 Maintaining window size by removing the leftmost element as window slides.

Line:

idx = bisect.bisect_left(window, nums[i - k])
window.pop(idx)

💡 Removal keeps window elements relevant to current position.

insert

Slide window: insert incoming element -3

Insert nums[4] = 5 into the window maintaining sorted order.

💡 Insertion keeps the window balanced and sorted for median calculation.

Line:

bisect.insort_left(window, nums[i])

💡 Insertion places new element correctly for median calculation.

compare

Calculate median of third window

Median is the middle element of [-3, -1, 5], which is -1.

💡 Median reflects the middle value after sliding the window.

Line:

result.append(get_median())

💡 Median updates as window slides, reflecting new data distribution.

delete

Slide window: remove outgoing element -1

Remove nums[2] = -1 from the window by locating and popping it.

💡 Removing the leftmost element keeps the window size constant.

Line:

idx = bisect.bisect_left(window, nums[i - k])
window.pop(idx)

💡 Removal keeps window elements relevant to current position.

insert

Slide window: insert incoming element 3

Insert nums[5] = 3 into the window maintaining sorted order.

💡 Insertion keeps the window balanced and sorted for median calculation.

Line:

bisect.insort_left(window, nums[i])

💡 Insertion places new element correctly for median calculation.

compare

Calculate median of fourth window

Median is the middle element of [-3, 3, 5], which is 3.

💡 Median reflects the middle value after sliding the window.

Line:

result.append(get_median())

💡 Median updates as window slides, reflecting new data distribution.

delete

Slide window: remove outgoing element -3

Remove nums[3] = -3 from the window by locating and popping it.

💡 Removing the leftmost element keeps the window size constant.

Line:

idx = bisect.bisect_left(window, nums[i - k])
window.pop(idx)

💡 Removal keeps window elements relevant to current position.

insert

Slide window: insert incoming element 6

Insert nums[6] = 6 into the window maintaining sorted order.

💡 Insertion keeps the window balanced and sorted for median calculation.

Line:

bisect.insort_left(window, nums[i])

💡 Insertion places new element correctly for median calculation.

compare

Calculate median of fifth window

Median is the middle element of [3, 5, 6], which is 5.

💡 Median reflects the middle value after sliding the window.

Line:

result.append(get_median())

💡 Median updates as window slides, reflecting new data distribution.

delete

Slide window: remove outgoing element 5

Remove nums[4] = 5 from the window by locating and popping it.

💡 Removing the leftmost element keeps the window size constant.

Line:

idx = bisect.bisect_left(window, nums[i - k])
window.pop(idx)

💡 Removal keeps window elements relevant to current position.

insert

Slide window: insert incoming element 7

Insert nums[7] = 7 into the window maintaining sorted order.

💡 Insertion keeps the window balanced and sorted for median calculation.

Line:

bisect.insort_left(window, nums[i])

💡 Insertion places new element correctly for median calculation.

compare

Calculate median of sixth window

Median is the middle element of [3, 6, 7], which is 6.

💡 Median reflects the middle value after sliding the window.

Line:

result.append(get_median())

💡 Median updates as window slides, reflecting new data distribution.

import bisect
from typing import List

def max_sliding_window_median(nums: List[int], k: int) -> List[float]:
    window = sorted(nums[:k])  # STEP 1: Initialize window
    result = []

    def get_median():
        if k % 2 == 1:
            return float(window[k // 2])  # STEP 2,5,8,11,14,17: Get median
        else:
            return (window[k // 2 - 1] + window[k // 2]) / 2

    result.append(get_median())  # STEP 2

    for i in range(k, len(nums)):
        idx = bisect.bisect_left(window, nums[i - k])  # STEP 3,6,9,12,15: Find outgoing element
        window.pop(idx)  # STEP 3,6,9,12,15: Remove outgoing element
        bisect.insort_left(window, nums[i])  # STEP 4,7,10,13,16: Insert incoming element
        result.append(get_median())  # STEP 5,8,11,14,17: Append median

    return result

if __name__ == '__main__':
    nums = [1,3,-1,-3,5,3,6,7]
    k = 3
    print(max_sliding_window_median(nums, k))

📊

Maximum Sliding Window Median - Watch the Algorithm Execute, Step by Step

Watching each insertion, removal, and median calculation helps you understand how the algorithm maintains a balanced window and efficiently finds medians without sorting from scratch each time.

insertmin|max-heap

-1

0

1

1

3

2

peekmin|max-heap

-1

0

1

1

3

2

Added: 1

deletemin|max-heap

-1

0

3

1

insertmin|max-heap

-3

0

-1

1

3

2

peekmin|max-heap

-3

0

-1

1

3

2

Added: -1

deletemin|max-heap

-3

0

-1

1

insertmin|max-heap

-3

0

-1

1

5

2

peekmin|max-heap

-3

0

-1

1

5

2

Added: -1

deletemin|max-heap

-3

0

5

1

insertmin|max-heap

-3

0

3

1

5

2

peekmin|max-heap

-3

0

3

1

5

2

Added: 3

deletemin|max-heap

3

0

5

1

insertmin|max-heap

3

0

5

1

6

2

peekmin|max-heap

3

0

5

1

6

2

Added: 5

deletemin|max-heap

3

0

6

1

insertmin|max-heap

3

0

6

1

7

2

peekmin|max-heap

3

0

6

1

7

2

Added: 6

Key Takeaways

✓ Maintaining a balanced data structure (two heaps or a sorted window) allows efficient median calculation as the window slides.

Without visualization, it's hard to see how insertions and removals keep the data balanced and why median extraction is efficient.

✓ Each sliding step involves removing the outgoing element and inserting the incoming element, both done via binary search to maintain order.

This shows why the algorithm avoids full re-sorting and achieves better performance.

✓ The median is always the middle element (or average of two middles) in the balanced window, reflecting the current window's data distribution.

Seeing the median update step-by-step clarifies how the data structure supports quick median retrieval.

Practice

1. Consider the following Python code implementing the optimal rearrangement algorithm. What is the output of rearrangeString("aabc", 2)?

easy

A. "abac"

B. "abca"

C. "aabc"

D. "" (empty string)

Solution

1. Step 1: Trace first iterations of the loop

   Initial freq: {a:2, b:1, c:1}, max_heap=[(-2,'a'),(-1,'b'),(-1,'c')]. Pop 'a', res=['a'], queue=[('a',-1)]. Queue size < k=2, continue.

2. Step 2: Next iterations and final string

   Pop 'b', res=['a','b'], queue=[('a',-1),('b',0)]. Queue size == k, pop front ('a',-1), since count<0, push back (-1,'a'). Next pop 'a', res=['a','b','a'], queue=[('b',0),('a',0)]. Pop front ('b',0), count not <0, no push. Pop 'c', res=['a','b','a','c'], queue=[('a',0),('c',0)]. Final string length matches input length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output "abac" respects k=2 spacing and uses all chars [OK]

Hint: Track heap pops and queue size carefully [OK]

Common Mistakes:

• Confusing when to push back characters into heap
• Off-by-one in decrementing counts
• Returning partial strings without length check

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

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