Advance 1: Find the Median from Data Stream/Sliding Window

https://leetcode.com/problems/sliding-window-median/

Question

You are 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 array for each window in the original array. Answers within $10^{-5}$ of the actual value will be accepted.

Hint

• What is the median?

  • it is the middle point in a dataset

  • it is half of the data points are smaller than the median, and half of the data points are larger.

  • max(smaller part) + min(larger part)

• find two data structures and maintain they balance

• Also, this concept can extend to 25th quantile, or whatever ?? quantile

Solution

High Level

• find two data structures to store all the elements, and make sure these two data structures satisfy the following two properties

  • value wise: max(the smaller half) < min(the larger half)

  • size wise:

    • when #element = old, smaller.size > larger.size + 1

    • when #element = even, smaller.size = larger.size

• By keeping these two data structures balanced, we can ensure that the median is either the maximum element of the max-heap or the minimum element of the min-heap.

Middle Level

• We would like to help some APIs

  • insert(int num)

  • delete(int num)

  • findMedian()

• for insert/ delete

  • 1) as we know the maximum(smaller half), and minimum(larger half), compare this num with these two

    • maximum(smaller half) &minimum(larger half)

    • to choose which half you would like to put this num in

  • 2) maintain the size property

• find median

  • #element == even?

    • (maximum(smaller half) + minimum(larger half) ) / 2

  • #element == old

    • maximum(smaller half)

Method 1 Two Heap

• insert(int num) ---> $O( \log n)$

• delete(int num)---> $O(n)$

• findMedian() --->$O(1)$

Method 2(not recommend) Two TreeMaps/ One TreeMap

• insert(int num) ---> $O( \log n)$

• delete(int num)---> $O(\log n)$

• findMedian() --->$O(1)$