Kth Largest Element in a Stream

In this class, We discuss Kth Largest Element in a Stream.

Readers can prepare an entire competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Given an input stream. 

The input is coming in a stream, assuming from the internet.

Here the elements are provided in an array. But assume coming in a stream.

Our task is to find the kth largest element for each element in the stream.

If the kth largest element does not exist, then print -1.

Example:

1) k=4 and n = 6

arr = [1,2,3,4,5,6]

Output: [-1,-1,-1,1,2,3]

2) k=4 and n=6

arr = [10, 2, 4, 9, 1, 11]

Output: [-1, -1, -1, 2, 2, 4]

Time complexity: O(Nlogk)

Space complexity: O(N)

Logic:

We can use insertion sort to arrange elements in ascending.

The insertion sort will take a time O(N^2).

If we go with min heap, we can solve it in O(Nlogk).

The step-by-step explanation is provided in the video.

Code:

import heapq

class Solution:

    def kthLargest(self, k, arr, n):

        # code here

        list = []

        min=[]

        for val in arr:

            if len(min) < k:

                heapq.heappush(min, val)

            else:

                if val > min[0]:

                    heapq.heappop(min)

                    heapq.heappush(min, val)

            if len(min) >= k:

                list.append(min[0])

            else:

                list.append(-1)

        return list

arr = [1, 2, 3, 4, 5, 6]

ob=Solution()

res = ob.kthLargest(4,arr,len(arr))

for x in res:

    print(“Kth largest element is”, x)