Sliding Window Median

Explore how to calculate the median for each sliding window in an integer array using heap data structures. This lesson helps you implement an optimized approach to manage dynamic data streams and understand median computations within moving windows, improving your problem-solving skills for coding interviews.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

Given an integer array, nums, and an integer, k, there is a sliding window of size k, which is moving from the very left to the very right of the array. We can only see the k numbers in the window. Each time the sliding window moves right by one position.

Given this scenario, return the median of the each window. Answers within $10^{-5}$ of the actual value will be accepted.

Constraints:

$1 \leq$ k $\leq$ nums.length $\leq 10^3$
$-2^{31} \leq$ nums[i] $\leq 2^{31} - 1$

Examples

JavaScript

usercode > Solution.js

import { MinHeap, MaxHeap } from './Heap.js'

/* The following definition is for MinHeap.

  You can use the same methods for MaxHeap.
  class MinHeap {

    size();          // return number of elements
    peek();          // return top element without removing
    push(val);       // insert element
    pop();           // remove and return top element
  }
*/

export function medianSlidingWindow(nums, k){

    // Replace this placeholder return statement with your code
    return [];
}

Sliding Window Median

Sliding Window Median

Statement

Examples

Understand the problem

Figure it out!

Try it yourself