Finding the k’th Largest Element in an Infinite Integer Stream

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.

Example:

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

Extra space allowed is O(n).

Recommended : Importance of Data Structures

Approach:
The idea is to solve this problem without any additional Data structure. 
1) Store all the elements of given array into vector and sort the vector in decreasing order. 
2) Now traverse through the given array from its last elements

• a) For every element of given array we need to print kth largest element of of the vector
• b) Also keep removing the current element of given array from vector.

Implementation in C++:

// CPP program to find k-th largest element in a 
// stream after every insertion.
#include <bits/stdc++.h>

using namespace std;

// utility functon for seaching an element in sorted array
int binarySearch(vector < int > vec, int target) {

  int low = 0, high = vec.size() - 1, mid;

  while (low < high) {
    mid = (low + high) / 2;
    if (vec[mid] == target) {
      return mid;

    } else if (vec[mid] > target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
}

vector < int > kthLargest(int k, int arr[], int n) {

  //Declaring and initializing vector with given arra elements.
  vector < int > UtillArr(arr, arr + n);

  //Sort the vector in decreasing array.
  sort(UtillArr.begin(), UtillArr.end(), greater < int > ());

  //array for storing our output.
  vector < int > ans;

  //traversing elements form end
  for (int i = n - 1; i >= 0; i--) {
    if (UtillArr.size() >= k) {
      //push back the k-th largest element from utillarr
      ans.push_back(UtillArr[k - 1]);

      //Now search the current element of arr in utillarr and delete it
      int ind = binarySearch(UtillArr, arr[i]);

      UtillArr.erase(UtillArr.begin() + ind);

    } else {
      ans.push_back(-1);
    }

  }
  //reverse the array ans for desired output
  reverse(ans.begin(), ans.end());

  //return the output array
  return ans;

}

// Driver code
int main() {
  int arr[] = {10, 20, 11, 70, 50, 40, 100, 55};
  int k = 3;
  int n = sizeof(arr) / sizeof(arr[0]);
  vector < int > ans = kthLargest(k, arr, n);
  for (int i = 0; i < ans.size(); i++)
    cout << ans[i] << " ";
  return 0;
}

Output:

-1 -1 10 11 20 40 50 55 

Time complexity: O(nlogn)
Space complexity: O(n)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.