Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given a list of numbers, the task is to insert these numbers into a stream and find the median of the stream after each insertion. If the median is a non-integer, consider it’s floor value.

The median of a sorted array is defined as the middle element when the number of elements is odd and the mean of the middle two elements when the number of elements is even.

```
{
"stream": [3, 8, 5, 2]
}
```

Output:

```
[3, 5, 5, 4]
```

Iteration | Stream | Sorted Stream | Median |
---|---|---|---|

1 | [3] | [3] | 3 |

2 | [3, 8] | [3, 8] | (3 + 8) / 2 => 5 |

3 | [3, 8, 5] | [3, 5, 8] | 5 |

4 | [3, 8, 5, 2] | [2, 3, 5, 8] | (3 + 5) / 2 => 4 |

Constraints:

- 1 <= length of stream <= 10
^{5} - 1 <= any value in the stream <= 10
^{5} - The stream can contain duplicates.

We have provided three solutions.

We will start with a brute-force and an optimized brute-force approach that solves the problem in polynomial time complexity, later we present an optimized solution that uses heap. Throughout this editorial, we will refer to the input array as `stream`

and its size as `n`

.

The idea is to follow the exact same steps described in the problem statement.

for `i`

= 1 to `n`

:

- Create an array
`current_stream`

containing`stream[1]`

,`stream[2]`

, ...,`stream[i]`

. - Sort
`current_stream`

. - Compute the median of the
`current_stream`

array.

O(n^{2} * log(n)).

To iterate in `n`

elements: O(n).

In each iteration,

- Create and sort the
`current_stream`

array: O(n * log(n)). - Compute median: O(1).

Total complexity: O(n^{2} * log(n)).

O(n).

Space used to create a temporary array in each iteration: O(n).

O(n).

Space used for input: O(n).

Auxiliary space used: O(n).

Space used for output: O(n).

So, total space complexity: O(n).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input array:
* Time: O(n^2 * log(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/
vector<int> online_median(vector<int> &stream) {
vector<int> medians;
for (int i = 1; i <= stream.size(); i++) {
// Slice the stream till i index.
vector<int> current_stream(stream.begin(), stream.begin() + i);
sort(current_stream.begin(), current_stream.end());
int median;
int size = current_stream.size();
if (size % 2 == 0)
median = (current_stream[size / 2] + current_stream[size / 2 - 1]) / 2;
else
median = current_stream[size / 2];
medians.push_back(median);
}
return medians;
}
```

As the name suggests, the solution will be similar to `brute_force_solution.cpp`

. We always need a sorted array after fetching a new element from the stream to compute the median, we can use the sorted array from the previous iteration and apply the concept of insertion sort where we insert this new element into the previously sorted array.

for `i`

= 1 to `n`

:

- Insert
`stream[i]`

to an already sorted substream`stream[1, 2, ..., i - 1]`

. - Compute the median of the substream
`stream[1, 2, ..., i]`

.

We use the concept of insertion sort to remove the log(n) factor from the time complexity and reduce the auxiliary space requirement to O(1).

O(n^{2}).

To iterate in `n`

elements: O(n).

In each iteration,

- Insert new element in the sorted array: O(n).
- Compute median: O(1).

Total complexity: O(n^{2}).

O(1).

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(n).

So, total space complexity: O(n).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input array:
* Time: O(n^2).
* Auxiliary space: O(1).
* Total space: O(n).
*/
vector<int> online_median(vector<int> &stream) {
vector<int> medians;
for (int i = 0; i < stream.size(); i++) {
// Applying insertion sort.
// Insert stream[i] in stream[0, 1,..., i - 1] which is already sorted.
for (int j = i - 1; j >= 0; j--) {
if (stream[j + 1] < stream[j])
swap(stream[j + 1], stream[j]);
else
break;
}
int median;
int current_elements = i + 1;
if (current_elements % 2 == 0)
median = (stream[current_elements / 2] + stream[current_elements / 2 - 1]) / 2;
else
median = stream[current_elements / 2];
medians.push_back(median);
}
return medians;
}
```

The median of an array can be computed only when the array is sorted. To add an element from the stream, we need to maintain a sorted array, and adding an element in the sorted array requires O(size*of*sorted_array) time. As we need only the middle element/s, this complexity can be improved by using a min-heap and a max-heap.

The min-heap will store the larger half of the stream and the max-heap will store the lower half of the sorted stream. For every element that is added from the stream, we keep the sizes of the heaps the same or they differ maximum by 1. Without the loss of generality, we will have the extra element in max-heap whenever required. This way, if the total size of the stream is odd, the element on top of the max-heap is our median, else the floor of the average of the elements on the top of the min-heap and the max-heap is our required value. Please have a look at the solution for a better understanding.

O(n * log(n)).

To iterate in `n`

elements: O(n).

In each iteration,

- Add OR remove element to/from heap: O(log(n)).
- Access top element of the heap: O(1).

Total complexity: O(n * log(n)).

O(n).

Space used for max-heap = O(n / 2).

Space used for min-heap = O(n / 2).

O(n).

Space used for input: O(n).

Auxiliary space used: O(n).

Space used for output: O(n).

So, total space complexity: O(n).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input array:
* Time: O(n * log(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/
priority_queue<int> max_heap; // To store the smaller half of the input numbers.
priority_queue<int, vector<int>, greater<int>> min_heap; // To store the larger half of the input numbers.
void add_new_element(int num) {
// Balancing heaps to make sure:
// - smaller half of input numbers are always in the max heap
// - larger half of input numbers are always in the min heap
max_heap.push(num);
min_heap.push(max_heap.top());
max_heap.pop();
// Maintain size property.
// 1. max_heap.size() = min_heap.size(), when number of elements is even
// 2. max_heap.size() = min_heap.size() + 1, when number of elements is odd
if (min_heap.size() > max_heap.size()) {
max_heap.push(min_heap.top());
min_heap.pop();
}
}
int get_current_stream_median() {
// If number of elements in the stream is even.
if (max_heap.size() == min_heap.size())
return (max_heap.top() + min_heap.top()) / 2;
// If number of elements in the stream is odd.
return max_heap.top();
}
vector<int> online_median(vector<int> &stream) {
vector<int> medians;
for (int i = 0; i < stream.size(); i++) {
add_new_element(stream[i]);
medians.push_back(get_current_stream_median());
}
return medians;
}
```

We hope that these solutions to online medium problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

Given a list of numbers, the task is to insert these numbers into a stream and find the median of the stream after each insertion. If the median is a non-integer, consider it’s floor value.

The median of a sorted array is defined as the middle element when the number of elements is odd and the mean of the middle two elements when the number of elements is even.

```
{
"stream": [3, 8, 5, 2]
}
```

Output:

```
[3, 5, 5, 4]
```

Iteration | Stream | Sorted Stream | Median |
---|---|---|---|

1 | [3] | [3] | 3 |

2 | [3, 8] | [3, 8] | (3 + 8) / 2 => 5 |

3 | [3, 8, 5] | [3, 5, 8] | 5 |

4 | [3, 8, 5, 2] | [2, 3, 5, 8] | (3 + 5) / 2 => 4 |

Constraints:

- 1 <= length of stream <= 10
^{5} - 1 <= any value in the stream <= 10
^{5} - The stream can contain duplicates.

We have provided three solutions.

We will start with a brute-force and an optimized brute-force approach that solves the problem in polynomial time complexity, later we present an optimized solution that uses heap. Throughout this editorial, we will refer to the input array as `stream`

and its size as `n`

.

The idea is to follow the exact same steps described in the problem statement.

for `i`

= 1 to `n`

:

- Create an array
`current_stream`

containing`stream[1]`

,`stream[2]`

, ...,`stream[i]`

. - Sort
`current_stream`

. - Compute the median of the
`current_stream`

array.

O(n^{2} * log(n)).

To iterate in `n`

elements: O(n).

In each iteration,

- Create and sort the
`current_stream`

array: O(n * log(n)). - Compute median: O(1).

Total complexity: O(n^{2} * log(n)).

O(n).

Space used to create a temporary array in each iteration: O(n).

O(n).

Space used for input: O(n).

Auxiliary space used: O(n).

Space used for output: O(n).

So, total space complexity: O(n).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input array:
* Time: O(n^2 * log(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/
vector<int> online_median(vector<int> &stream) {
vector<int> medians;
for (int i = 1; i <= stream.size(); i++) {
// Slice the stream till i index.
vector<int> current_stream(stream.begin(), stream.begin() + i);
sort(current_stream.begin(), current_stream.end());
int median;
int size = current_stream.size();
if (size % 2 == 0)
median = (current_stream[size / 2] + current_stream[size / 2 - 1]) / 2;
else
median = current_stream[size / 2];
medians.push_back(median);
}
return medians;
}
```

As the name suggests, the solution will be similar to `brute_force_solution.cpp`

. We always need a sorted array after fetching a new element from the stream to compute the median, we can use the sorted array from the previous iteration and apply the concept of insertion sort where we insert this new element into the previously sorted array.

for `i`

= 1 to `n`

:

- Insert
`stream[i]`

to an already sorted substream`stream[1, 2, ..., i - 1]`

. - Compute the median of the substream
`stream[1, 2, ..., i]`

.

We use the concept of insertion sort to remove the log(n) factor from the time complexity and reduce the auxiliary space requirement to O(1).

O(n^{2}).

To iterate in `n`

elements: O(n).

In each iteration,

- Insert new element in the sorted array: O(n).
- Compute median: O(1).

Total complexity: O(n^{2}).

O(1).

O(n).

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(n).

So, total space complexity: O(n).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input array:
* Time: O(n^2).
* Auxiliary space: O(1).
* Total space: O(n).
*/
vector<int> online_median(vector<int> &stream) {
vector<int> medians;
for (int i = 0; i < stream.size(); i++) {
// Applying insertion sort.
// Insert stream[i] in stream[0, 1,..., i - 1] which is already sorted.
for (int j = i - 1; j >= 0; j--) {
if (stream[j + 1] < stream[j])
swap(stream[j + 1], stream[j]);
else
break;
}
int median;
int current_elements = i + 1;
if (current_elements % 2 == 0)
median = (stream[current_elements / 2] + stream[current_elements / 2 - 1]) / 2;
else
median = stream[current_elements / 2];
medians.push_back(median);
}
return medians;
}
```

The median of an array can be computed only when the array is sorted. To add an element from the stream, we need to maintain a sorted array, and adding an element in the sorted array requires O(size*of*sorted_array) time. As we need only the middle element/s, this complexity can be improved by using a min-heap and a max-heap.

The min-heap will store the larger half of the stream and the max-heap will store the lower half of the sorted stream. For every element that is added from the stream, we keep the sizes of the heaps the same or they differ maximum by 1. Without the loss of generality, we will have the extra element in max-heap whenever required. This way, if the total size of the stream is odd, the element on top of the max-heap is our median, else the floor of the average of the elements on the top of the min-heap and the max-heap is our required value. Please have a look at the solution for a better understanding.

O(n * log(n)).

To iterate in `n`

elements: O(n).

In each iteration,

- Add OR remove element to/from heap: O(log(n)).
- Access top element of the heap: O(1).

Total complexity: O(n * log(n)).

O(n).

Space used for max-heap = O(n / 2).

Space used for min-heap = O(n / 2).

O(n).

Space used for input: O(n).

Auxiliary space used: O(n).

Space used for output: O(n).

So, total space complexity: O(n).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input array:
* Time: O(n * log(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/
priority_queue<int> max_heap; // To store the smaller half of the input numbers.
priority_queue<int, vector<int>, greater<int>> min_heap; // To store the larger half of the input numbers.
void add_new_element(int num) {
// Balancing heaps to make sure:
// - smaller half of input numbers are always in the max heap
// - larger half of input numbers are always in the min heap
max_heap.push(num);
min_heap.push(max_heap.top());
max_heap.pop();
// Maintain size property.
// 1. max_heap.size() = min_heap.size(), when number of elements is even
// 2. max_heap.size() = min_heap.size() + 1, when number of elements is odd
if (min_heap.size() > max_heap.size()) {
max_heap.push(min_heap.top());
min_heap.pop();
}
}
int get_current_stream_median() {
// If number of elements in the stream is even.
if (max_heap.size() == min_heap.size())
return (max_heap.top() + min_heap.top()) / 2;
// If number of elements in the stream is odd.
return max_heap.top();
}
vector<int> online_median(vector<int> &stream) {
vector<int> medians;
for (int i = 0; i < stream.size(); i++) {
add_new_element(stream[i]);
medians.push_back(get_current_stream_median());
}
return medians;
}
```

We hope that these solutions to online medium problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart