Given an input stream arr[] of n integers. Find the K^{th} largest element (not K^{th} largest unique element) for each element in the stream and if the K^{th} element doesn't exist, return -1.
Example 1:
Input:
k = 4, n = 6
arr[] = {1, 2, 3, 4, 5, 6}
Output:
-1 -1 -1 1 2 3
Explanation:
k = 4
For 1, the 4th largest element doesn't
exist so we print -1.
For 2, the 4th largest element doesn't
exist so we print -1.
For 3, the 4th largest element doesn't
exist so we print -1.
For 4, the 4th largest element is 1.
For 5, the 4th largest element is 2.
for 6, the 4th largest element is 3.
Example 2:
Input:
k = 1, n = 2
arr[] = {3, 4}
Output:
3 4 
Explanation: 
For the 1st and 2nd element the 1st largest 
element is itself.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function kthLargest() which takes 2 Integers k, and n and also an array arr[] of size n as input and returns the k^{th }largest element in the stream.
 
Expected Time Complexity: O(nlogk)
Expected Auxiliary Space: O(n)
 
Constraints:
1 ≤ k ≤ n ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

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

        # code here 

Solutions:
from heapq import *

class Solution:

	def kthLargest(self, k, arr, n):
		if k == 1:
			return arr
		res = [-1] * (k - 1)
		heap = []
		for elm in arr:
			if len(heap) < k:
				heappush(heap, elm)
			else:
				res.append(heap[0])
				if elm > heap[0]:
					heappop(heap)
					heappush(heap, elm)
		else:
			res.append(heap[0])
		return res


from heapq import *

class Solution:

	def kthLargest(self, k, arr, n):
		ans = [-1] * (k - 1)
		heap = []
		for ele in arr:
			if len(heap) < k:
				heappush(heap, ele)
			else:
				top = heap[0]
				ans.append(top)
				if ele > top:
					heappop(heap)
					heappush(heap, ele)
		else:
			ans.append(heap[0])
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		minheap = []
		ans = [-1] * n
		for i in range(n):
			heapq.heappush(minheap, arr[i])
			if len(minheap) == k:
				ans[i] = minheap[0]
			elif len(minheap) > k:
				heapq.heappop(minheap)
				ans[i] = minheap[0]
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		heap = []
		result = []
		count = 0
		for i in arr:
			if count < k:
				heapq.heappush(heap, i)
				count += 1
			elif count > -k and heap[0] < i:
				heapq.heappop(heap)
				heapq.heappush(heap, i)
			if count < k:
				result.append(-1)
			else:
				result.append(heap[0])
		return result


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		h = []
		res = []

		def add(item):
			if len(h) < k:
				heapq.heappush(h, item)
			else:
				heapq.heappushpop(h, item)
		for a in arr:
			add(a)
			if len(h) < k:
				res.append(-1)
			else:
				tmp = heapq.heappop(h)
				res.append(tmp)
				heapq.heappush(h, tmp)
		return res


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		min = []
		l = []
		for val in arr:
			if len(min) < k:
				heapq.heappush(min, val)
			elif val > min[0]:
				heapq.heappop(min)
				heapq.heappush(min, val)
			if len(min) >= k:
				l += [min[0]]
			else:
				l += [-1]
		return l


from heapq import *

class Solution:

	def kthLargest(self, k, arr, n):
		result = []
		minheap = []
		count = 0
		for i in range(0, len(arr)):
			if len(minheap) < k:
				heappush(minheap, arr[i])
				count += 1
			elif arr[i] > minheap[0]:
				heappop(minheap)
				count -= 1
				heappush(minheap, arr[i])
				count += 1
			if count >= k:
				result.append(minheap[0])
			else:
				result.append(-1)
		return result


from heapq import *

class Solution:

	def kthLargest(self, k, arr, n):
		ans = [-1] * (k - 1)
		minHeap = []
		for i in range(n):
			ele = arr[i]
			if len(minHeap) < k:
				heappush(minHeap, ele)
			elif ele > minHeap[0]:
				ans.append(heappop(minHeap))
				heappush(minHeap, ele)
			else:
				ans.append(minHeap[0])
		ans.append(minHeap[0])
		return ans


from heapq import heapify, heappush, heappop, heapreplace

class Solution:

	def kthLargest(self, k, arr, n):
		res = []
		h = []
		heapify(h)
		for el in arr:
			if len(h) < k:
				heappush(h, el)
				if len(h) < k:
					res.append(-1)
				else:
					res.append(h[0])
			else:
				if el > h[0]:
					heapreplace(h, el)
				res.append(h[0])
		return res


import heapq as hq

class Solution:

	def kthLargest(self, k, arr, n):
		heap = []
		for (i, x) in enumerate(arr):
			hq.heappush(heap, x)
			if len(heap) < k:
				arr[i] = -1
			elif len(heap) == k:
				arr[i] = heap[0]
			else:
				hq.heappop(heap)
				arr[i] = heap[0]
		return arr


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		ans = []
		heap = []
		for i in arr:
			if k > 0:
				heapq.heappush(heap, i)
				k -= 1
			elif heap[0] < i:
				heapq.heapreplace(heap, i)
			if k > 0:
				ans.append(-1)
			else:
				ans.append(heap[0])
		return ans


import heapq as hq

class Solution:

	def kthLargest(self, k, arr, n):
		(temp, count, res) = ([], 0, [])
		for i in arr:
			if count < k:
				hq.heappush(temp, i)
				count += 1
			elif count >= k and temp[0] < i:
				hq.heappop(temp)
				hq.heappush(temp, i)
			if count < k:
				res.append(-1)
			else:
				res.append(temp[0])
		return res


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		res = []
		h = []
		for i in range(k - 1):
			h.append(arr[i])
			res.append(-1)
		heapq.heapify(h)
		old = -1
		for i in range(k - 1, len(arr)):
			heapq.heappush(h, max(old, arr[i]))
			old = heapq.heappop(h)
			res.append(old)
		return res


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		ans = []
		heap = []
		for i in range(k - 1):
			ans.append(-1)
			heapq.heappush(heap, arr[i])
		for i in range(k - 1, n):
			heapq.heappush(heap, arr[i])
			if len(heap) > k:
				heapq.heappop(heap)
			ans.append(heap[0])
		return ans


import heapq

class Solution:

	def min_heap(self, stack, vals):
		stack.append(vals)
		for i in range(len(stack) - 1, 0, -1):
			if stack[i][0] < stack[i - 1][0]:
				(stack[i], stack[i - 1]) = (stack[i - 1], stack[i])

	def kthLargest(self, k, arr, n):
		if n < k:
			return [-1] * k
		stack = list()
		ans = list()
		j = 0
		for i in range(n):
			heapq.heappush(stack, arr[i])
			if len(stack) > k:
				while len(stack) > k:
					heapq.heappop(stack)
			if len(stack) == k:
				ans.append(stack[0])
			else:
				ans.append(-1)
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		if k == 1:
			return arr
		heap = []
		heapq.heapify(heap)
		res = []
		for i in range(len(arr)):
			heapq.heappush(heap, arr[i])
			if i + 1 < k:
				res.append(-1)
			else:
				if len(heap) > k:
					heapq.heappop(heap)
				val = heapq.heappop(heap)
				res.append(val)
				heapq.heappush(heap, val)
		return res


import heapq

class Solution:

	def insert_at_sorted_pos(self, temp, data):
		temp.append(data)
		j = len(temp) - 2
		while j >= 0 and temp[j] > data:
			temp[j + 1] = temp[j]
			j -= 1
		temp[j + 1] = data

	def kthLargestBF(self, k, arr, n):
		temp = []
		ans = []
		for i in range(n):
			self.insert_at_sorted_pos(temp, arr[i])
			idx = len(temp) - k
			if idx < 0:
				ans.append(-1)
			else:
				ans.append(temp[idx])
		return ans

	def kthLargest(self, k, arr, n):
		min_heap = []
		ans = []
		for x in arr:
			heapq.heappush(min_heap, x)
			if len(min_heap) < k:
				ans.append(-1)
			elif len(min_heap) == k:
				ans.append(min_heap[0])
			else:
				heapq.heappop(min_heap)
				ans.append(min_heap[0])
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		(count, res, ans) = (0, [], [])
		for i in range(n):
			if len(res) < k:
				heapq.heappush(res, arr[i])
				count += 1
			elif res[0] < arr[i]:
				heapq.heappop(res)
				count -= 1
				heapq.heappush(res, arr[i])
				count += 1
			if count >= k:
				ans.append(res[0])
			else:
				ans.append(-1)
		return ans


class Solution:

	def kthLargest(self, k, arr, n):
		from heapq import heappop, heappush, heappushpop
		s = []
		ans = []
		f = []
		for i in range(n):
			num = arr[i]
			if len(f) < k - 1:
				heappush(f, -heappushpop(s, -num))
				ans.append(-1)
			else:
				heappush(s, -heappushpop(f, num))
				ans.append(-s[0])
		return ans


import heapq as h

class Solution:

	def kthLargest(self, k, arr, n):
		l = []
		l1 = []
		h.heapify(l1)
		for i in arr:
			if len(l1) == k:
				if l1[0] <= i:
					h.heappop(l1)
					h.heappush(l1, i)
			if len(l1) < k:
				h.heappush(l1, i)
			if len(l1) < k:
				l.append(-1)
			if len(l1) == k:
				l.append(l1[0])
		return l


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		h = []
		heapq.heapify(h)
		ans = []
		for val in arr[:k]:
			heapq.heappush(h, val)
			ans.append(-1)
		ans[-1] = h[0]
		for val in arr[k:]:
			if val <= h[0]:
				ans.append(h[0])
				continue
			heapq.heapreplace(h, val)
			ans.append(h[0])
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		ans = ['-1'] * len(arr)
		heap = []
		i = 0
		for x in arr:
			if len(heap) < k:
				heapq.heappush(heap, x)
			elif x > heap[0]:
				heapq.heapreplace(heap, x)
			if len(heap) >= k:
				ans[i] = str(heap[0])
			i += 1
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		res = [-1] * (k - 1)
		hp = arr[:k]
		heapq.heapify(hp)
		for i in range(k, n):
			res.append(hp[0])
			if arr[i] > hp[0]:
				heapq.heapreplace(hp, arr[i])
		res.append(hp[0])
		return res


class Solution:

	def kthLargest(self, k, arr, n):
		import heapq
		lst = []
		ans = []
		heapq.heapify(lst)
		for i in arr:
			heapq.heappush(lst, i)
			if len(lst) < k:
				ans.append(-1)
			else:
				x = heapq.heappop(lst)
				if len(ans) > 0 and ans[-1] > x:
					ans.append(ans[-1])
				else:
					ans.append(x)
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		Ans = []
		A = []
		for i in range(n):
			if len(A) < k:
				heapq.heappush(A, arr[i])
			elif len(A) > 0 and A[0] < arr[i]:
				heapq.heappop(A)
				heapq.heappush(A, arr[i])
			if i < k - 1:
				Ans.append(-1)
			else:
				Ans.append(A[0])
		return Ans


from heapq import heapify, heappush, heappop

class Solution:

	def kthLargest(self, k, arr, n):
		d = []
		heapify(d)
		e = []
		for i in arr:
			heappush(d, i)
			if len(d) > k:
				heappop(d)
			if len(d) < k:
				e.append(-1)
			else:
				e.append(d[0])
		return e


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		heap = arr[:k]
		heapq.heapify(heap)
		output = [-1 for _ in range(k - 1)]
		output.append(heap[0])
		for item in arr[k:]:
			if item > heap[0]:
				heapq.heappushpop(heap, item)
			output.append(heap[0])
		return output


from heapq import heappop, heappush

class Solution:

	def kthLargest(self, k, arr, n):
		pq = []
		res = []
		for i in range(n):
			heappush(pq, arr[i])
			if len(pq) < k:
				res.append(-1)
			else:
				if len(pq) > k:
					heappop(pq)
				res.append(pq[0])
		return res


from queue import PriorityQueue
import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		heap = []
		sol = []
		for i in range(n):
			if i < k:
				heapq.heappush(heap, arr[i])
			elif arr[i] > heap[0]:
				heapq.heapreplace(heap, arr[i])
			if i < k - 1:
				sol.append(-1)
			else:
				sol.append(heap[0])
		return sol


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		res = []
		heap = []
		heapq.heapify(heap)
		for i in range(k - 1):
			res.append(-1)
		for i in range(k - 1):
			heapq.heappush(heap, arr[i])
		i = k - 1
		while i < n:
			if len(heap) < k:
				heapq.heappush(heap, arr[i])
			elif arr[i] > heap[0]:
				heapq.heappop(heap)
				heapq.heappush(heap, arr[i])
			Min = heap[0]
			res.append(Min)
			i += 1
		return res


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		(temp, count, res) = ([], 0, [])
		for i in arr:
			temp.append(i)
			count += 1
			heapq.heapify(temp)
			if count >= k:
				res.append(temp[-1 * k])
			else:
				res.append(-1)
		return res

	def kthLargest(self, k, arr, n):
		le = 0
		res = []
		mini = []
		for i in range(n):
			if le < k:
				heapq.heappush(mini, arr[i])
				le += 1
			elif mini[0] < arr[i]:
				heapq.heappop(mini)
				heapq.heappush(mini, arr[i])
			if le >= k:
				res.append(mini[0])
			else:
				res.append(-1)
		return res


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		n = len(arr)
		k = min(k, n)
		min_heap = []
		out = []
		for i in range(k):
			heapq.heappush(min_heap, arr[i])
			out.append(-1)
		out[-1] = min_heap[0]
		for i in range(k, n):
			if arr[i] > min_heap[0]:
				heapq.heappop(min_heap)
				heapq.heappush(min_heap, arr[i])
			out.append(min_heap[0])
		return out


from collections import deque
import bisect
import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		heap = []
		kth_largest = []
		for x in arr:
			if len(heap) < k:
				heapq.heappush(heap, x)
			elif x > heap[0]:
				heapq.heapreplace(heap, x)
			if len(heap) == k:
				kth_largest.append(heap[0])
			else:
				kth_largest.append(-1)
		return kth_largest


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		ans = []
		for i in range(k - 1):
			ans.append(-1)
		temp = arr[:k]
		heapq.heapify(temp)
		ans.append(temp[0])
		for i in range(k, n):
			if arr[i] > temp[0]:
				heapq.heappop(temp)
				heapq.heappush(temp, arr[i])
			ans.append(temp[0])
		return ans


from heapq import heapify, heapreplace

class Solution:

	def kthLargest(self, k, A, n):
		H = A[:k]
		heapify(H)
		ans = [-1] * (k - 1) + [H[0]]
		for i in range(k, n):
			if A[i] > H[0]:
				heapreplace(H, A[i])
			ans.append(H[0])
		return ans


import heapq

class Solution:

	def kthLargest(self, k, arr, n):
		result = []
		min_heap = []
		heapq.heapify(min_heap)
		min_heap_len = 0
		for i in range(n):
			if min_heap_len < k:
				heapq.heappush(min_heap, arr[i])
				min_heap_len += 1
			elif arr[i] > min_heap[0]:
				heapq.heappop(min_heap)
				heapq.heappush(min_heap, arr[i])
			if min_heap_len < k:
				result.append(-1)
			else:
				result.append(min_heap[0])
		return result


from heapq import heappush, heappop

class Solution:

	def kthLargest(self, k, arr, n):
		s = []
		ans = [-1] * n
		for (index, i) in enumerate(arr):
			heappush(s, i)
			if len(s) < k:
				continue
			if len(s) > k:
				heappop(s)
			ans[index] = s[0]
		return ans


class Solution:

	def kthLargest(self, k, arr, n):
		min_heap = []
		import heapq
		min_heap = arr[:k]
		heapq.heapify(min_heap)
		ans = [-1 for i in range(n)]
		ans[k - 1] = min_heap[0]
		for i in range(k, n):
			if arr[i] > min_heap[0]:
				heapq.heapreplace(min_heap, arr[i])
			ans[i] = min_heap[0]
		return ans


import heapq as hp

class Solution:

	def kthLargest(self, k, arr, n):
		(heap, ans) = ([], [])
		for i in arr:
			hp.heappush(heap, i)
			if len(heap) < k:
				ans.append(-1)
			elif len(heap) == k:
				ans.append(heap[0])
			else:
				hp.heappop(heap)
				ans.append(heap[0])
		return ans


from heapq import heappop, heappush, heappushpop

class Solution:

	def kthLargest(self, k, arr, n):
		q = []
		ans = []
		size = 0
		for i in arr:
			if size < k:
				heappush(q, i)
				size += 1
				if size == k:
					ans.append(q[0])
				else:
					ans.append(-1)
			else:
				heappushpop(q, i)
				ans.append(q[0])
		return ans