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 an initial list along with another list of numbers to be appended with the initial list and an integer *K*, return an array consisting of the *K*th largest element after adding each element from the first list to the second list.

**Example**

Input: [ 2, [4, 6], [5, 2, 20] ]

Output: [5, 5, 6]

**Notes**

Constraints:

- 1 <= length of both lists <= 10^5.
- 1 <=
*K*<= length of initial list - 0 <= any value in the list <= 10^9.
- The stream can contain duplicates.

We have provided two solutions.

We will start with a brute-force approach that solves the problem in polynomial time complexity, later we present an optimized linear time complexity solution. We will refer to the initial list as *intial_stream* and the second list as *append_stream*.

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

for i = 1 to *size_of_append_stream*:

- Add *append_stream[i] *to *initial_stream*.

- Sort *initial_stream* in non-decreasing order.

- The Kth element from the end will be the Kth largest element.

**Time Complexity:**

O(*|append_stream*| * (|*append_stream*| + *|initial_stream*|)* * *log(|*append_stream*| + *|initial_stream*|)).

To sort the initial stream = O(*|initial_stream*| * log(*|initial_stream*|)).

To add an element from *append_stream* to the sorted stream = O((|*append_stream*| + *|initial_stream*|) * log(|*append_stream*| + *|initial_stream*|)).

We add |*append_stream*| number of elements to the sorted stream.

**Auxiliary Space Used:**

O(|*append_stream*|).

Memory used to add elements from *append_stream* to *initial_stream* = O(|*append_stream*|).

**Space Complexity:**

O(|*initial_stream*| + |*append_stream*|).

Memory used for input = O(|*initial_stream*| + |*append_stream*|).

Memory used for output = O(|*append_stream*|).

Auxiliary space = O(|*append_stream*|).

Total space complexity = O(|*initial_stream|* + |*append_stream*|).

The idea is to keep track of only the *K* largest elements of the stream. Create a min-heap storing the *K* largest elements from *initial_stream*. To create such a heap, we can sort the *inital_stream* and push *K *largest elements in the heap but this will require O(|*inital_stream|* * log(|*inital_stream|*)). Instead, we will directly push elements from *inital_stream* to min-heap to achieve a complexity of O(|*inital_stream|* * log(*K*)). While pushing the elements we will keep a check such that the size of min-heap does not exceed *K* which can be achieved by popping the top element of the heap when its size becomes (*K + 1*).

- If the new element is smaller than the top element of the heap, ignore it

- else remove the topmost element of the heap and insert the new element in the heap. To remove or insert a new element, the time complexity is O(log(*K)*).

The top element of the heap is always the Kth largest element of the current stream.

**Note: **It is possible to get a solution using a max-heap also instead of a min-heap, but would require some extra handling i.e. maintaining a max-heap of size (number_of_elements_at_time - K + 1) to get the Kth largest element.

**Time Complexity:**

O( log(*K*) * ( |*initial_stream*| + |*append_stream*|* *)).

To maintain a heap of size *K* = O(log(K)).

We push and pop every element of the initial and append stream at most once.

**Auxiliary Space Used:**

O(*K*).

Memory used to maintain a heap of size *K* = O(*K*).

**Space Complexity:**

O(|*initial_stream*| + |*append_stream*|* *+ *K*).

Memory used for input = O(|*initial_stream*| + |*append_stream*|).

Memory used for output = O(|*append_stream*|).

Auxiliary space = O(*K*).

Total space complexity = O(|*initial_stream*| + |*append_stream*|* *+ *K*).

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

Given an initial list along with another list of numbers to be appended with the initial list and an integer *K*, return an array consisting of the *K*th largest element after adding each element from the first list to the second list.

**Example**

Input: [ 2, [4, 6], [5, 2, 20] ]

Output: [5, 5, 6]

**Notes**

Constraints:

- 1 <= length of both lists <= 10^5.
- 1 <=
*K*<= length of initial list - 0 <= any value in the list <= 10^9.
- The stream can contain duplicates.

We have provided two solutions.

We will start with a brute-force approach that solves the problem in polynomial time complexity, later we present an optimized linear time complexity solution. We will refer to the initial list as *intial_stream* and the second list as *append_stream*.

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

for i = 1 to *size_of_append_stream*:

- Add *append_stream[i] *to *initial_stream*.

- Sort *initial_stream* in non-decreasing order.

- The Kth element from the end will be the Kth largest element.

**Time Complexity:**

O(*|append_stream*| * (|*append_stream*| + *|initial_stream*|)* * *log(|*append_stream*| + *|initial_stream*|)).

To sort the initial stream = O(*|initial_stream*| * log(*|initial_stream*|)).

To add an element from *append_stream* to the sorted stream = O((|*append_stream*| + *|initial_stream*|) * log(|*append_stream*| + *|initial_stream*|)).

We add |*append_stream*| number of elements to the sorted stream.

**Auxiliary Space Used:**

O(|*append_stream*|).

Memory used to add elements from *append_stream* to *initial_stream* = O(|*append_stream*|).

**Space Complexity:**

O(|*initial_stream*| + |*append_stream*|).

Memory used for input = O(|*initial_stream*| + |*append_stream*|).

Memory used for output = O(|*append_stream*|).

Auxiliary space = O(|*append_stream*|).

Total space complexity = O(|*initial_stream|* + |*append_stream*|).

The idea is to keep track of only the *K* largest elements of the stream. Create a min-heap storing the *K* largest elements from *initial_stream*. To create such a heap, we can sort the *inital_stream* and push *K *largest elements in the heap but this will require O(|*inital_stream|* * log(|*inital_stream|*)). Instead, we will directly push elements from *inital_stream* to min-heap to achieve a complexity of O(|*inital_stream|* * log(*K*)). While pushing the elements we will keep a check such that the size of min-heap does not exceed *K* which can be achieved by popping the top element of the heap when its size becomes (*K + 1*).

- If the new element is smaller than the top element of the heap, ignore it

- else remove the topmost element of the heap and insert the new element in the heap. To remove or insert a new element, the time complexity is O(log(*K)*).

The top element of the heap is always the Kth largest element of the current stream.

**Note: **It is possible to get a solution using a max-heap also instead of a min-heap, but would require some extra handling i.e. maintaining a max-heap of size (number_of_elements_at_time - K + 1) to get the Kth largest element.

**Time Complexity:**

O( log(*K*) * ( |*initial_stream*| + |*append_stream*|* *)).

To maintain a heap of size *K* = O(log(K)).

We push and pop every element of the initial and append stream at most once.

**Auxiliary Space Used:**

O(*K*).

Memory used to maintain a heap of size *K* = O(*K*).

**Space Complexity:**

O(|*initial_stream*| + |*append_stream*|* *+ *K*).

Memory used for input = O(|*initial_stream*| + |*append_stream*|).

Memory used for output = O(|*append_stream*|).

Auxiliary space = O(*K*).

Total space complexity = O(|*initial_stream*| + |*append_stream*|* *+ *K*).

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

Hosted By

Ryan Valles

Founder, Interview Kickstart