This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:`[2,3,4]`

, the median is `3`

`[2,3]`

, the median is `(2 + 3) / 2 = 2.5`

Given an array *nums*, 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. Your job is to output the median array for each window in the original array.

For example,

Given *nums* = `[1,3,-1,-3,5,3,6,7]`

, and *k* = 3.

Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6

Therefore, return the median sliding window as `[1,-1,-1,3,5,6]`

.

**Note: **

You may assume `k`

is always valid, ie: `k`

is always smaller than input array's size for non-empty array.

b'

\n### A word of advice

\n## Solution

\n

\n#### Approach #1 Simple Sorting [Time Limit Exceeded / Barely Accepted]

\n

\n#### Approach #2 Two Heaps! (Lazy Removal) [Accepted]

\n

\n#### Approach #3 Two Multisets! [Accepted]

\n

\n#### Approach #4 Multiset and Two Pointers [Accepted]

\n

\n#### Further Thoughts

\n

\n

'
\n\n

\nThis problem is a companion problem to 295. Find Median From Data Stream. This means that a lot of approaches to solve this problem are based on the methods to solve 295. Find Median From Data Stream. Perhaps try that problem before you approach this one.

\n\n

**Intuition**

Do what the question says.

\n**Algorithm**

Store the numbers in a window container of size . The following operations must take place:

\n- \n
**Inserting**the incoming element. \n**Deleting**the outgoing element. \n**Sorting**the window to find the medians. \n

One primitive approach is to copy consecutive elements from the input to the window and keep sorting these every time. This constitutes duplication of effort.

\nWe can do a bit better if we instead *insert* and *delete* one element per window shift. The challenge then is to maintain the window as **sorted**, before and after the *insert* and *delete* operations.

**C++ [Time Limit Exceeded]**

**Python [Accepted]**

Python comes with an excellent `bisect`

module to help perform efficient insert operations on lists while maintaining their sorted property.

**Complexity Analysis**

- \n
- \n
Time complexity: to .

\n- \n
- Copying elements into the container takes about time each. This happens about times. \n
- \n
Sorting for each of the sliding window instances takes about time each.

\n \n - \n
Bisected insertion or deletion takes about for searching and for actual shifting of elements. This takes place about times.

\n \n

\n - \n
Space complexity: extra linear space for the window container.

\n \n

\n

**Intuition**

The idea is the same as Approach #3 from 295. Find Median From Data Stream. The only additional requirement is removing the outgoing elements from the window.

\nSince the window elements are stored in heaps, deleting elements that are not at the top of the heaps is a pain.

\nSome languages (like **Java**) provide implementations of the `PriorityQueue`

class that allow for removing *arbitrarily* placed elements. Generally, using such features is not efficient nor is their portability assured.

Assuming that only the tops of heaps (and by extension the `PriorityQueue`

class) are accessible, we need to find a way to efficiently invalidate and remove elements that are moving out of the sliding window.

At this point, an important thing to notice is the fact that if the two heaps are balanced, only the top of the heaps are actually needed to find the medians. This means that as long as we can somehow keep the heaps balanced, we could also keep some extraneous elements.

\nThus, we can use hash-tables to keep track of invalidated elements. Once they reach the heap tops, we remove them from the heaps. This is the lazy removal technique.

\nAn immediate challenge at this point is balancing the heaps while keeping extraneous elements. This is done by actually moving some elements to the heap which has extraneous elements, from the other heap. This cancels out the effect of having extraneous elements and maintains the invariant that the heaps are balanced.

\n**NOTE:** When we talk about keeping the heaps balanced, we are **not** referring to the actual heap sizes. We are only concerned with valid elements and hence when we talk about balancing heaps, we are referring to count of such elements.

**Algorithm**

- \n
- \n
Two priority queues:

\n- \n
- A max-heap
`lo`

to store the smaller half of the numbers \n - A min-heap
`hi`

to store the larger half of the numbers \n

\n - A max-heap
- \n
A hash-map or hash-table

\n`hash_table`

for keeping track of invalid numbers. It holds the count of the occurrences of all such numbers that have been invalidated and yet remain in the heaps. \n - \n
The max-heap

\n`lo`

is allowed to store, at worst, one more element more than the min-heap`hi`

. Hence if we have processed elements:- \n
- If , then
`lo`

is allowed to hold elements, while`hi`

can hold elements. \n - If , then both heaps are balanced and hold elements each. \n

This gives us the nice property that when the heaps are perfectly balanced, the median can be derived from the tops of both heaps. Otherwise, the top of the max-heap

\n`lo`

holds the legitimate median. \n - If , then

**NOTE:** As mentioned before, when we are talking about keeping the heaps balanced, the actual sizes of the heaps are irrelevant. Only the count of valid elements in both heaps matter.

- \n
- \n
Keep a

\n`balance`

factor. It indicates three situations:- \n
`balance`

: Both heaps are balanced or nearly balanced. \n`balance`

:`lo`

needs more valid elements. Elements from`hi`

are moved to`lo`

. \n`balance`

:`hi`

needs more valid elements. Elements from`lo`

are moved to`hi`

. \n

\n - \n
Inserting an incoming number

\n`in_num`

:- \n
- \n
If

\n`in_num`

is less than or equal to the top element of`lo`

, then it can be inserted to`lo`

. However this unbalances`hi`

(`hi`

has lesser valid elements now). Hence`balance`

is incremented. \n - \n
Otherwise,

\n`in_num`

must be added to`hi`

. Obviously, now`lo`

is unbalanced. Hence`balance`

is decremented. \n

\n - \n
- \n
Lazy removal of an outgoing number

\n`out_num`

:- \n
- If
`out_num`

is present in`lo`

, then invalidating this occurrence will unbalance`lo`

itself. Hence`balance`

must be decremented. \n - \n
If

\n`out_num`

is present in`hi`

, then invalidating this occurrence will unbalance`hi`

itself. Hence`balance`

must be incremented. \n - \n
We increment the count of this element in the hash_table table.

\n \n - Once an invalid element reaches either of the heap tops, we remove them and decrement their counts in the hash_table table. \n

\n - If

**Complexity Analysis**

- \n
- \n
Time complexity: .

\n- \n
- Either (or sometimes both) of the heaps gets every element inserted into it at least once. Collectively each of those takes about time. That is such insertions. \n
- About removals from the top of the heaps take place (the number of sliding window instances). Each of those takes about time. \n
- Hash table operations are assumed to take time each. This happens roughly the same number of times as removals from heaps take place. \n

\n - \n
Space complexity: extra linear space.

\n- \n
- The heaps collectively require space. \n
- The hash table needs about space. \n

\n

\n

**Intuition**

One can see that `multiset`

s are a great way to keep elements sorted while providing efficient access to the first and last elements. Inserting and deleting arbitrary elements are also fairly efficient operations in a `multiset`

. (Refer to Approach #4 Intuition for 295. Find Median From Data Stream)

Thus, if the previous approach gives you too much heartburn, consider replacing the use of `priority_queue`

with `multiset`

.

**Algorithm**

Inserting or deleting an element is straight-forward. Balancing the heaps takes the same route as Approach #3 of 295. Find Median From Data Stream.

\n\n**Complexity Analysis**

- \n
- \n
Time complexity: .

\n- \n
- At worst, there are three set insertions and three set deletions from the start or end. Each of these takes about time. \n
- Finding the mean takes constant time since the start or ends of sets are directly accessible. \n
- Each of these steps takes place about times (the number of sliding window instances). \n

\n - \n
Space complexity: extra linear space to hold contents of the window.

\n \n

\n

**Intuition**

This is same as Approach #4 for 295. Find Median From Data Stream.

\n\n\nBut, we don\'t actually need two pointers.

\n

Median elements are derived using a single iterator position (when the window size is odd) or two consecutive iterator positions (when is even). Hence keeping track of *only* one pointer is sufficient. The other pointer can be *implicitly derived* when required.

**Algorithm**

- \n
- \n
A single iterator

\n`mid`

, which iterates over the`window`

multiset. It is analogous to`upper_median`

in Approach #4 for 295. Find Median From Data Stream.`lower_median`

is*implicitly derived*from`mid`

. It\'s either equal to`mid`

(when the window size is odd) or`prev(mid)`

^{1}. \n - \n
We start with populating our multiset

\n`window`

with the first elements. We set`mid`

to the indexed element in`window`

(`0`

-based indexing; Multisets always maintain their sorted property). \n - \n
While inserting an element

\n`num`

into`window`

, three cases arise:- \n
- \n

\n`num`

is less than the value of upper median`mid`

. \n - \n

\n`num`

is greater than the value of upper median`mid`

. \n - \n

\n`num`

is equal to the value of upper median`mid`

. This situation is often handled as language-dependent. Since C++`multiset`

insert elements at the end of their equal range, this situation is essentially the same as the previous case. \n - \n
For the first case,

\n`num`

is inserted before the upper median element`mid`

. Thus`mid`

now, no longer points to the indexed element. In fact it points to the indexed element. We fix that by decrementing`mid`

. \n - \n
For the second and third cases,

\n`num`

is inserted after the upper median element`mid`

and hence does not spoil the`mid`

iterator. It still points to the indexed element. \n - \n
Of course, the window size just increased to in all three cases. That will easily be fixed by removing the element that is about to exit the window.

\n \n

\n - \n
- \n
While removing an element

\n`num`

, the same three cases arise as when we wanted to insert an element:- \n
- \n

\n`num`

is less than the value of upper median`mid`

. \n - \n

\n`num`

is greater than the value of upper median`mid`

. \n - \n

\n`num`

is equal to the value of upper median`mid`

. Since`mid`

will point to the first occurrence of`num`

in the multiset`window`

and we deterministically remove the first occurrence (take note that we use`std::multiset::lower_bound()`

^{2}to find the correct occurrence to erase), this case is handled in the same manner as the first case. \n - \n
In the first and third cases, removing

\n`num`

will spoil the`mid`

iterator. Thus we need to fix that by incrementing`mid`

before we remove that element. \n - \n
For the second case, the

\n`mid`

iterator is not spoiled. No further action is required. \n - \n
Once this element has been removed, the window size returns to being .

\n \n

\n - \n
- \n
After insertion of the incoming element and removal of the outgoing element, we are left again with some nice invariants:

\n- \n
- Window size is again . \n
- The window is still fully sorted. \n
`mid`

still points to the indexed element. \n

\n - \n
Finding the median of the window is easy! It is simply the

\n**mean**of the elements pointed to by the two pointers`lo_median`

and`hi_median`

. In our case those are`mid`

or`prev(mid)`

(as decided by whether is odd or even) , and`mid`

respectively. \n

^{3}

**Complexity Analysis**

- \n
- \n
Time complexity: .

\n- \n
- Initializing
`mid`

takes about time. \n - Inserting or deleting a number takes time for a standard
`multiset`

scheme.^{4}\n - Finding the mean takes constant time since the median elements are directly accessible from
`mid`

iterator. \n - The last two steps take place about times (the number of sliding window instances). \n

\n - Initializing
- \n
Space complexity: extra linear space to hold contents of the window.

\n \n

\n

As noted before, this problem is essentially an extension to 295. Find Median From Data Stream. That problem had a lot of ways to go about, that frankly, are not of much use in an interview. But they are interesting to follow all the same. If you are interested take a look here. Try extending those methods to this problem.

\n\n

Analysis written by @babhishek21.

\n\n

\n

\n\n

- \n
- \n

\n`std::prev()`

is a C++ method to find the previous element to the current one being pointed to by an iterator.\xc2\xa0\xe2\x86\xa9 \n - \n
Had we used

\n`std::multiset::find()`

, there was no guarantee that the first occurrence of`num`

would be found. Although the contrary did happen in all of our tests, I don\'t recommend using it. Your mileage may vary.\xc2\xa0\xe2\x86\xa9 \n - \n
Shout-out to @votrubac and @StefanPochmann!\xc2\xa0\xe2\x86\xa9

\n \n - \n
Hinting can reduce that to amortized constant time.\xc2\xa0\xe2\x86\xa9

\n \n