Given an infinite stream of integers, find the k’th largest element at any point of time. It may be assumed that 1 <= k <= n.
Input:
stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}
k = 3
Output: {_, _, 10, 11, 20, 40, 50, 50, ...}
Extra space allowed is O(k).
The idea is to use min heap.
- Store first k elements in min heap.
- For every element from (k+1)-th to n-th, do following.
- Print root of heap.
- If current element is more than root of heap, pop root and insert
Implementation:
C++
// CPP program to find k-th largest element in a // stream after every insertion.#include <bits/stdc++.h>using namespace std;int kthLargest(int stream[], int n, int k){ // Create a min heap and store first k-1 elements // of stream into priority_queue<int, vector<int>, greater<int> > pq; // Push first k elements and print "_" (k-1) times for (int i=0; i<k-1; i++) { pq.push(stream[i]); cout << "_ "; } pq.push(stream[k-1]); for (int i=k; i<n; i++) { // We must insert last element before we // decide last k-th largest output. cout << pq.top() << " "; if (stream[i] > pq.top()) { pq.pop(); pq.push(stream[i]); } } // Print last k-th largest element (after // (inserting last element) cout << pq.top();}// Driver codeint main(){ int arr[] = {10, 20, 11, 70, 50, 40, 100, 55}; int k = 3; int n = sizeof(arr)/sizeof(arr[0]); kthLargest(arr, n, k); return 0;} |
Java
// Java Program for the above approach import java.util.*;class GFG{ static void kthLargest(int stream[], int n, int k) { // Create a min heap and store first k-1 elements // of stream into Vector<Integer> pq = new Vector<Integer>(n); // Push first k elements and print "_" (k-1) times for (int i = 0; i < k - 1; i++) { pq.add(stream[i]); System.out.print("_ "); } pq.add(stream[k - 1]); for (int i = k; i < n; i++) { // We must insert last element before we // decide last k-th largest output. Collections.sort(pq); System.out.print(pq.get(0) + " "); if (stream[i] > pq.get(0)) { pq.remove(0); pq.add(stream[i]); } } // Print last k-th largest element (after // (inserting last element) Collections.sort(pq); System.out.print(pq.get(0)); } // Driver code public static void main(String[] args) { int arr[] = {10, 20, 11, 70, 50, 40, 100, 55}; int k = 3; int n = arr.length; kthLargest(arr, n, k); }}// This code is contributed by divyeshrabadiya07. |
Python3
## Python Program for the above approachimport heapqdef kthLargest(stream, n, k): # Create a min heap and store first k-1 elements # of stream into pq = [] # Push first k elements and print "_" (k-1) times for i in range(k - 1): pq.append(stream[i]) print("_ ", end = "") pq.append(stream[k - 1]) # creating min heap and maintaining the heap # property heapq.heapify(pq) for i in range(k,n): # We must insert last element before we # decide last k-th largest output. print(pq[0],end=" ") if (stream[i]>pq[0]): #deleting the last element from the min heap pq[0]=pq[-1] pq.pop() pq.append(stream[i]) heapq.heapify(pq); ## Print last k-th largest element (after # (inserting last element) print(pq[0])# Driver codearr = [10, 20, 11, 70, 50, 40, 100, 55]k = 3n = len(arr)kthLargest(arr, n, k)'''Code is contributed by Rajat Kumar''' |
C#
// C# program to find k-th largest element in a // stream after every insertion. using System;using System.Collections.Generic;class GFG { static void kthLargest(int[] stream, int n, int k) { // Create a min heap and store first k-1 elements // of stream into List<int> pq = new List<int>(); // Push first k elements and print "_" (k-1) times for (int i = 0; i < k - 1; i++) { pq.Add(stream[i]); Console.Write("_ "); } pq.Add(stream[k - 1]); for (int i = k; i < n; i++) { // We must insert last element before we // decide last k-th largest output. pq.Sort(); Console.Write(pq[0] + " "); if (stream[i] > pq[0]) { pq.RemoveAt(0); pq.Add(stream[i]); } } // Print last k-th largest element (after // (inserting last element) pq.Sort(); Console.Write(pq[0]); } // Driver code static void Main() { int[] arr = {10, 20, 11, 70, 50, 40, 100, 55}; int k = 3; int n = arr.Length; kthLargest(arr, n, k); }}// This code is contributed by divyesh072019. |
Javascript
<script>// JavaScript program to find k-th largest element in a// stream after every insertion.function kthLargest(stream, n, k) { // Create a min heap and store first k-1 elements // of stream into let pq = new Array(); // Push first k elements and print "_" (k-1) times for (let i = 0; i < k - 1; i++) { pq.push(stream[i]); document.write("_ "); } pq.push(stream[k - 1]); for (let i = k; i < n; i++) { // We must insert last element before we // decide last k-th largest output. pq.sort((a, b) => a - b); document.write(pq[0] + " "); if (stream[i] > pq[0]) { pq.shift(0); pq.push(stream[i]); } } // Print last k-th largest element (after // (inserting last element) pq.sort((a, b) => a - b); document.write(pq[0]);}// Driver codelet arr = [10, 20, 11, 70, 50, 40, 100, 55];let k = 3;let n = arr.length;kthLargest(arr, n, k);// This code is contributed by _saurabh_jaiswal</script> |
Output
_ _ 10 11 20 40 50 55
If stream contains elements of non-primitive types, we may define our own compactor function and create a priority_queue accordingly.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
