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

1-sliding-window-median.js

// nums array of numbers, k sliding window size
// return median of every sliding window
// basically we keep two heaps,
// left heap is a max heap where all the numbers lt or equal to median are kept
// right heap is a min heap where all the numbers gt than median are kept
// this way sliding window median is always either left heap top, or avg of two tops
// elements who exit the sliding window are ignored unless they pop to the top of either heap
// then we drop them (we keep track of them leaving the window using a hashmap)
// we also need to make sure that right heap contains exactly half of the current sliding window numbers,
// so we rebalance the heaps if for example an element exited the window from the left heap, and entered to the right heap
export function medianSlidingWindow(nums, k) {
  // max heap, elements lt or equal to current median
  const leftHeap = new Heap();
  // min heap, elements gt than current median
  const rightHeap = new Heap();

  // first push all elements of the initial window to the max heap
  for (let i = 0; i < k; ++i) {
    // we make min heap implementation behave like max heap by inverting the sign
    leftHeap.push(-nums[i]);
  }

  // move half of the elements to the min heap
  for (let i = 0; i < Math.floor(k / 2); ++i) {
    rightHeap.push(-leftHeap.deleteTop());
  }

  const getMedian = () => {
    return k % 2 === 0
      ? (-leftHeap.peekTop() + rightHeap.peekTop()) / 2
      : -leftHeap.peekTop();
  };

  // median of the initial sliding window
  const medians = [getMedian()];

  // start moving the sliding window
  // start points to the first element of the sliding window
  let start = 1;
  // end points to the last elements of the sliding window
  let end = k;
  // keep track of elements leaving the sliding window
  const outLog = {};

  // keep moving the sliding window forward until we reach the end of the array
  while (end < nums.length) {
    // an element who is leaving the window
    const leaving = nums[start - 1];
    // and element who is entering the window
    const entering = nums[end];
    // if balance is negative, we need to move elements from right to left heap
    // if balance is positive, we need to move elements from left to right heap
    // if balance is 0, rebalancing is not needed
    let balance = 0;

    // save leaving element to the log
    outLog[leaving] = (outLog[leaving] ?? 0) + 1;

    if (leaving <= -leftHeap.peekTop()) {
      // element exited the left heap
      balance -= 1;
    } else {
      // element exited the right heap
      balance += 1;
      console.log(leaving, "is leaving right heap");
    }

    if (entering <= getMedian()) {
      // new element entered the left heap
      leftHeap.push(-entering);
      balance += 1;
    } else {
      // new element entered the right heap
      rightHeap.push(entering);
      balance -= 1;
    }

    // handle rebalancing
    if (balance > 0) {
      rightHeap.push(-leftHeap.deleteTop());
    } else if (balance < 0) {
      leftHeap.push(-rightHeap.deleteTop());
    }

    // keep dropping elements from the top of either heap,
    // if those elements are recorded as exited the window on this step or on previous steps
    while (outLog[-leftHeap.peekTop()] > 0) {
      outLog[-leftHeap.deleteTop()] -= 1;
    }
    while (outLog[rightHeap.peekTop()] > 0) {
      outLog[rightHeap.deleteTop()] -= 1;
    }

    medians.push(getMedian());

    // slide the window forward
    start += 1;
    end += 1;
  }

  return medians;
}

2-README.md