Open In App

K’th largest element in a stream

Last Updated : 30 Dec, 2022
Improve
Improve
Like Article
Like
Save
Share
Report

Given an infinite stream of integers, find the Kth largest element at any point of time.

Note: Here we have a stream instead of a whole array and we are allowed to store only K elements.

Examples: 

Input: stream[] = {10, 20, 11, 70, 50, 40, 100, 5, . . .}, K = 3
Output: {_,   _, 10, 11, 20, 40, 50,  50, . . .}

Input: stream[] = {2, 5, 1, 7, 9, . . .}, K = 2
Output: {_, 2, 2, 5, 7, . . .} 

Naive Approach: To solve the problem follow the below idea:

Keep an array of size K. The idea is to keep the array sorted so that the Kth largest element can be found in O(1) time (we just need to return the first element of the array, if the array is sorted in increasing order

How to process a new element of the stream? 

For every new element in the stream, check if the new element is smaller than the current Kth largest element. If yes, then ignore it. If no, then remove the smallest element from the array and insert the new element in sorted order. 

The time complexity of processing a new element is O(K)

Kth largest element in a stream using a self-balancing binary search tree:

To solve the problem follow the below idea:

Create a self-balancing binary search tree and for every new element in the stream, check if the new element is smaller than the current k’th largest element. If yes, then ignore it. If no, then remove the smallest element from the tree and insert a new element. 

The Kth largest element can be found in O(log K) time.

Kth largest element in a stream using a Min-Heap:

To solve the problem follow the below idea:

An Efficient Solution is to use a Min Heap of size K to store K largest elements of the stream. The Kth largest element is always at the root and can be found in O(1) time

How to process a new element of the stream? 

Compare the new element with the root of the heap. If a new element is smaller, then ignore it. Otherwise, replace the root with a new element and call heapify for the root of the modified heap

Below is the implementation of the above approach:

CPP




// A C++ program to find k'th
// smallest element in a stream
#include <bits/stdc++.h>
using namespace std;
 
// Prototype of a utility function
// to swap two integers
void swap(int* x, int* y);
 
// A class for Min Heap
class MinHeap {
    int* harr; // pointer to array of elements in heap
    int capacity; // maximum possible size of min heap
    int heap_size; // Current number of elements in min heap
public:
    MinHeap(int a[], int size); // Constructor
    void buildHeap();
    void MinHeapify(
        int i); // To minheapify subtree rooted with index i
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }
    int extractMin(); // extracts root (minimum) element
    int getMin() { return harr[0]; }
 
    // to replace root with new node x and heapify() new
    // root
    void replaceMin(int x)
    {
        harr[0] = x;
        MinHeapify(0);
    }
};
 
MinHeap::MinHeap(int a[], int size)
{
    heap_size = size;
    harr = a; // store address of array
}
 
void MinHeap::buildHeap()
{
    int i = (heap_size - 1) / 2;
    while (i >= 0) {
        MinHeapify(i);
        i--;
    }
}
 
// Method to remove minimum element
// (or root) from min heap
int MinHeap::extractMin()
{
    if (heap_size == 0)
        return INT_MAX;
 
    // Store the minimum value.
    int root = harr[0];
 
    // If there are more than 1 items,
    // move the last item to
    // root and call heapify.
    if (heap_size > 1) {
        harr[0] = harr[heap_size - 1];
        MinHeapify(0);
    }
    heap_size--;
 
    return root;
}
 
// A recursive method to heapify a subtree with root at
// given index This method assumes that the subtrees are
// already heapified
void MinHeap::MinHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i) {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}
 
// A utility function to swap two elements
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
 
// Function to return k'th largest element from input stream
void kthLargest(int k, vector<int>& A)
{
    // count is total no. of elements in stream seen so far
    int count = 0, x; // x is for new element
 
    // Create a min heap of size k
    int* arr = new int[k];
    MinHeap mh(arr, k);
 
    for (auto& x : A) {
 
        // Nothing much to do for first k-1 elements
        if (count < k - 1) {
            arr[count] = x;
            count++;
 
            cout << "Kth largest element is -1 " << endl;
        }
 
        else {
            // If this is k'th element, then store it
            // and build the heap created above
            if (count == k - 1) {
                arr[count] = x;
                mh.buildHeap();
            }
 
            else {
                // If next element is greater than
                // k'th largest, then replace the root
                if (x > mh.getMin())
                    mh.replaceMin(x); // replaceMin calls
                                      // heapify()
            }
 
            // Root of heap is k'th largest element
            cout << "Kth largest element is "
                 << mh.getMin() << endl;
            count++;
        }
    }
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5, 6 };
    int K = 3;
 
    // Function call
    kthLargest(K, arr);
    return 0;
}


Java




// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    /*
    using min heap DS
 
    how data are stored in min Heap DS
           1
         2   3
    if k==3 , then top element of heap
    itself the kth largest largest element
 
    */
    static PriorityQueue<Integer> min;
    static int k;
 
    static List<Integer> getAllKthNumber(int arr[])
    {
 
        // list to store kth largest number
        List<Integer> list = new ArrayList<>();
 
        // one by one adding values to the min heap
        for (int val : arr) {
 
            // if the heap size is less than k , we add to
            // the heap
            if (min.size() < k)
                min.add(val);
 
            /*
            otherwise ,
            first we  compare the current value with the
            min heap TOP value
 
            if TOP val > current element , no need to
            remove TOP , bocause it will be the largest kth
            element anyhow
 
            else  we need to update the kth largest element
            by removing the top lowest element
            */
 
            else {
                if (val > min.peek()) {
                    min.poll();
                    min.add(val);
                }
            }
 
            // if heap size >=k we add
            // kth largest element
            // otherwise -1
 
            if (min.size() >= k)
                list.add(min.peek());
            else
                list.add(-1);
        }
        return list;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        min = new PriorityQueue<>();
 
        k = 3;
 
        int arr[] = { 1, 2, 3, 4, 5, 6 };
 
        // Function call
        List<Integer> res = getAllKthNumber(arr);
 
        for (int x : res)
            System.out.println("Kth largest element is "
                               + x);
    }
 
    // This code is Contributed by Pradeep Mondal P
}


Python




# Python program for the above approach
import heapq
 
# min heap DS
min = []
k = 3
 
# function to get all kth number
def getAllKthNumber(arr):
 
    # list to store kth largest number
    list = []
 
    # one by one adding values to the min heap
    for val in arr:
 
        # if the heap size is less than k , we add to
        # the heap
        if len(min) < k:
            heapq.heappush(min, val)
 
        # otherwise ,
        # first we compare the current value with the
        # min heap TOP value
 
        # if TOP val > current element , no need to
        # remove TOP , bocause it will be the largest kth
        # element anyhow
 
        # else we need to update the kth largest element
        # by removing the top lowest element
        else:
            if val > min[0]:
                heapq.heappop(min)
                heapq.heappush(min, val)
 
        # if heap size >=k we add
        # kth largest element
        # otherwise -1
        if len(min) >= k:
            list.append(min[0])
        else:
            list.append(-1)
    return list
 
# Driver Code
arr = [1, 2, 3, 4, 5, 6]
 
# Function call
res = getAllKthNumber(arr)
 
for x in res:
    print("Kth largest element is", x)
 
# This code is contributed by adityamaharshi21


C#




// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
    /*
    using min heap DS
 
    how data are stored in min Heap DS
           1
         2   3
    if k==3 , then top element of heap
    itself the kth largest largest element
 
    */
    static Queue<int> min;
    static int k;
 
    static List<int> getAllKthNumber(int[] arr)
    {
 
        // list to store kth largest number
        List<int> list = new List<int>();
 
        // one by one adding values to the min heap
        foreach(int val in arr)
        {
 
            // if the heap size is less than k , we add to
            // the heap
            if (min.Count < k)
                min.Enqueue(val);
 
            /*
            otherwise ,
            first we  compare the current value with the
            min heap TOP value
 
            if TOP val > current element , no need to
            remove TOP , bocause it will be the largest kth
            element anyhow
 
            else  we need to update the kth largest element
            by removing the top lowest element
            */
            else {
                if (val > min.Peek()) {
                    min.Dequeue();
                    min.Enqueue(val);
                }
            }
 
            // if heap size >=k we add
            // kth largest element
            // otherwise -1
 
            if (min.Count >= k)
                list.Add(min.Peek());
            else
                list.Add(-1);
        }
        return list;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        min = new Queue<int>();
        k = 3;
        int[] arr = { 1, 2, 3, 4, 5, 6 };
 
        // Function call
        List<int> res = getAllKthNumber(arr);
        foreach(int x in res) Console.Write(
            "Kth largest element is " + x + "\n");
    }
}
 
// This code is contributed by shikhasingrajput


Javascript




function getAllKthNumber(arr) {
    // min heap DS
    const min = [];
    const k = 3;
 
    // list to store kth largest number
    const list = [];
 
    // one by one adding values to the min heap
    for (const val of arr) {
        // if the heap size is less than k , we add to
        // the heap
        if (min.length < k) {
            min.push(val);
            min.sort((a, b) => a - b);
        }
        // otherwise ,
        // first we compare the current value with the
        // min heap TOP value
 
        // if TOP val > current element , no need to
        // remove TOP , bocause it will be the largest kth
        // element anyhow
 
        // else we need to update the kth largest element
        // by removing the top lowest element
        else {
            if (val > min[0]) {
                min.shift();
                min.push(val);
                min.sort((a, b) => a - b);
            }
        }
 
        // if heap size >=k we add
        // kth largest element
        // otherwise -1
        if (min.length >= k) {
            list.push(min[0]);
        } else {
            list.push(-1);
        }
    }
    return list;
}
 
// Driver Code
const arr = [1, 2, 3, 4, 5, 6];
 
// Function call
const res = getAllKthNumber(arr);
 
for (const x of res) {
    console.log('Kth largest element is', x);
}


Output

Kth largest element is -1 
Kth largest element is -1 
Kth largest element is 1
Kth largest element is 2
Kth largest element is 3
Kth largest element is 4

Time Complexity: O(N * log K)
Auxiliary Space: O(K)

Below is the implementation of the above approach using priority-queue:

C++




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
vector<int> kthLargest(int k, int arr[], int n)
{
    vector<int> ans(n);
 
    // Creating a min-heap using priority queue
    priority_queue<int, vector<int>, greater<int> > pq;
 
    // Iterating through each element
    for (int i = 0; i < n; i++) {
        // If size of priority
        // queue is less than k
        if (pq.size() < k)
            pq.push(arr[i]);
        else {
            if (arr[i] > pq.top()) {
                pq.pop();
                pq.push(arr[i]);
            }
        }
 
        // If size is less than k
        if (pq.size() < k)
            ans[i] = -1;
        else
            ans[i] = pq.top();
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int n = 6;
    int arr[n] = { 1, 2, 3, 4, 5, 6 };
    int k = 4;
 
    // Function call
    vector<int> v = kthLargest(k, arr, n);
    for (auto it : v)
        cout << it << " ";
    return 0;
}


Java




// Java program for the above approach
import java.util.*;
 
class GFG {
 
    static int[] kthLargest(int k, int arr[], int n)
    {
        int[] ans = new int[n];
 
        // Creating a min-heap using priority queue
        PriorityQueue<Integer> pq
            = new PriorityQueue<>((a, b) -> a - b);
 
        // Iterating through each element
        for (int i = 0; i < n; i++) {
 
            // If size of priority
            // queue is less than k
            if (pq.size() < k)
                pq.add(arr[i]);
            else {
                if (arr[i] > pq.peek()) {
                    pq.remove();
                    pq.add(arr[i]);
                }
            }
 
            // If size is less than k
            if (pq.size() < k)
                ans[i] = -1;
            else
                ans[i] = pq.peek();
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 6;
        int arr[] = { 1, 2, 3, 4, 5, 6 };
        int k = 4;
 
        // Function call
        int[] v = kthLargest(k, arr, n);
        for (int it : v)
            System.out.print(it + " ");
    }
}
 
// This code is contributed by shikhasingrajput


Python3




# Python3 program for the above approach
from queue import PriorityQueue
 
 
def kthLargest(k,  arr,  n):
    ans = [0]*n
 
    # Creating a min-heap using priority queue
    pq = PriorityQueue()
 
    # Iterating through each element
    for i in range(n):
        # If size of priority
        # queue is less than k
        if (pq.qsize() < k):
            pq.put(arr[i])
        else:
            if (arr[i] > pq.queue[0]):
                pq.get()
                pq.put(arr[i])
 
    # If size is less than k
        if (pq.qsize() < k):
            ans[i] = -1
        else:
            ans[i] = pq.queue[0]
 
    return ans
 
 
# Driver Code
if __name__ == "__main__":
    n = 6
    arr = [1, 2, 3, 4, 5, 6]
    k = 4
 
    # Function call
    v = kthLargest(k, arr, n)
    print(*v)
 
# This code is contributed by Lovely Jain


C#




// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
 
    static int[] kthLargest(int k, int[] arr, int n)
    {
        int[] ans = new int[n];
 
        // Creating a min-heap using priority queue
        List<int> pq = new List<int>();
 
        // Iterating through each element
        for (int i = 0; i < n; i++) {
 
            // If size of priority
            // queue is less than k
            if (pq.Count < k)
                pq.Add(arr[i]);
            else {
                if (arr[i] > pq[0]) {
                    pq.Sort();
                    pq.RemoveAt(0);
                    pq.Add(arr[i]);
                }
            }
 
            // If size is less than k
            if (pq.Count < k)
                ans[i] = -1;
            else
                ans[i] = pq[0];
        }
 
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int n = 6;
        int[] arr = { 1, 2, 3, 4, 5, 6 };
        int k = 4;
 
        // Function call
        int[] v = kthLargest(k, arr, n);
        foreach(int it in v) Console.Write(it + " ");
    }
}
 
// This code contributed by shikhasingrajput


Javascript




// JavaScript program for the above approach
 
function kthLargest(k, arr, n) {
    const ans = new Array(n);
 
    // Creating a min-heap using priority queue
    const pq = [];
 
    // Iterating through each element
    for (let i = 0; i < n; i++) {
        // If size of priority queue is less than k
        if (pq.length < k) pq.push(arr[i]);
        else {
            if (arr[i] > pq[0]) {
                pq.sort();
                pq.shift();
                pq.push(arr[i]);
            }
        }
 
        // If size is less than k
        if (pq.length < k) ans[i] = -1;
        else ans[i] = pq[0];
    }
 
    return ans;
}
 
// Driver Code
const n = 6;
const arr = [1, 2, 3, 4, 5, 6];
const k = 4;
 
// Function call
const v = kthLargest(k, arr, n);
console.log(v.join(' '));
 
// This code is contributed by aadityamaharshi21.


Output

-1 -1 -1 1 2 3 

Time Complexity: O(N * log K) 
Auxiliary Space: O(K)

Related Articles:
K’th Smallest/Largest Element in Unsorted Array | Set 1 
K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)



Previous Article
Next Article

Similar Reads

Java Program to Find the K'th largest element in a stream
Given an infinite stream of integers, find the k'th largest element at any point of time.Example: 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). Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. We have discussed different appro
4 min read
C++ Program to Find the K'th largest element in a stream
Given an infinite stream of integers, find the k'th largest element at any point of time.Example: Input:stream[] = {10, 20, 11, 70, 50, 40, 100, 5, ...}k = 3Output: {_, _, 10, 11, 20, 40, 50, 50, ...} Extra space allowed is O(k). Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. We have discussed different approach
7 min read
Largest element smaller than current element on left for every element in Array
Given an array arr[] of the positive integers of size N, the task is to find the largest element on the left side of each index which is smaller than the element present at that index. Note: If no such element is found then print -1. Examples: Input: arr[] = {2, 5, 10} Output: -1 2 5 Explanation : Index 0: There are no elements before it So Print -
11 min read
Largest triplet product in a stream
Given a stream of integers represented as arr[]. For each index i from 0 to n-1, print the multiplication of largest, second largest, third largest element of the subarray arr[0...i]. If i &lt; 2 print -1. Examples: Input : arr[] = {1, 2, 3, 4, 5} Output :-1 -1 6 24 60 Explanation : for i = 2 only three elements are there {1, 2, 3} so answer is 6.
5 min read
Count of subarrays with largest element at least twice the largest of remaining elements
Given an array arr[] consisting of N positive integers, the task is to find the count of subarrays such that the maximum element of the subarray is greater than twice the maximum of all other elements of the array. Examples: Input: arr[] = {1, 6, 10, 9, 7, 3}Output: 4Explanation:Below are the subarrays satisfying the given condition: Consider the s
14 min read
Remaining array element after repeated removal of last element and subtraction of each element from next adjacent element
Given an array arr[] consisting of N integers, the task is to find the remaining array element after subtracting each element from its next adjacent element and removing the last array element repeatedly. Examples: Input: arr[] = {3, 4, 2, 1}Output: 4Explanation:Operation 1: The array arr[] modifies to {4 - 3, 2 - 4, 1 - 2} = {1, -2, -1}.Operation
8 min read
Rank of an element in a stream
Given a stream of integers, look up the rank of a given integer x. The rank of an integer in-stream is "Total number of elements less than or equal to x (not including x)".If an element is not found in the stream or is the smallest in the stream, return -1. Examples: Input : arr[] = {10, 20, 15, 3, 4, 4, 1} x = 4; Output : Rank of 4 in stream is: 3
11 min read
Replace elements with absolute difference of smallest element on left and largest element on right
Given an array arr[] of N integers. The task is to replace all the elements of the array by the absolute difference of the smallest element on its left and the largest element on its right.Examples: Input: arr[] = {1, 5, 2, 4, 3} Output: 5 3 3 2 1 ElementSmallest on its leftLargest on its rightAbsolute difference1NULL5551432143413231NULL1 Input: ar
15+ min read
Array formed from difference of each element from the largest element in the given array
Given an array arr[], the task is to find the array formed from the difference of each element from the largest element in the given array. Example: Input: arr[] = {3, 6, 9, 2,6} Output: {6, 3, 0, 7, 3} Explanation: Largest element of the array = 9 Therefore difference of arr[i] from 9: Element 1: 9 - 3 = 6 Element 2: 9 - 6 = 3 Element 3: 9 - 9 = 0
5 min read
Find Array formed by adding each element of given array with largest element in new array to its left
Given an array A of size N, the task is to find the resultant array formed by adding each element of the given array with the largest element in the new array to its left.Examples: Input: arr[] = {5, 1, 6, -3, 2} Output: {5, 6, 12, 9, 14} Element A0: No element if present at its left. Hence the element at 0th index of the resultant array = 5 Elemen
6 min read