10

Find Kth Largest/Smallest element in a Queue

 1 year ago
source link: https://www.geeksforgeeks.org/find-kth-largest-smallest-element-in-a-queue/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Find Kth Largest/Smallest element in a Queue

Given a queue of integers and an integer K, our task is to write a program that efficiently finds Kth largest/smallest element present in the queue.Return -1 if the number of unique elements inside the queue is less than K.

Examples:

Input: Queue = {15, 27, 18, 13}, K = 2
Output: 18
Explanation: Among 15(front), 27, 18 and 13(back), 18 is the second(Kth) largest.

Input: Queue = {12, 25, 29, 16, 32}, K = 3
Output: 25
Explanation: Among 12(front), 25, 29, 16 and 32(back), 25 is the third(Kth) largest.

Approach: To solve the problem follow the below idea:

The idea to solve the problem is to insert all the queue elements into a set. And then return the K’th largest/smallest element from the set.

Follow the given steps to solve the problem:

  • First, check if the size of the queue is less than K. If so, it returns -1, as it is not possible to find the K’th largest/smallest unique element in a queue with less than K elements.
  • Now, store every element of the queue into the set st from the queue while popping items from it.
  • Now, if K is greater than the size of the set st then return -1, as the total number of unique elements is less than K.
  • Create a variable ind for index and initialize it by 1.
  • Now traverse over sorted elements in the set st and check if the current element index is equal to K (for smallest) and N+1-K (for largest), where N is the size of the set st.
  • If Index matches, return the value at that index.

Below is the implementation of the above approach to find K’th largest:

  • Python3
// C++ program to find the Kth largest element
// present in the queue
#include <bits/stdc++.h>
using namespace std;

// Function which return Kth largest element
// of the queue
int kElement(queue<int> q, int K)
{

    // If queue size is less than K
    // then return -1
    if (q.size() < K)
        return -1;

    // Declare SET st
    set<int> st;

    // Loop to insert every element of queue
    // inside set
    while (!q.empty()) {
        // Inserting current front element
        // inside set
        st.insert(q.front());

        // pop current front element
        q.pop();
    }

    // To store set size/length
    int N = st.size();

    // Check if set size is less than K
    if (N < K)
        return -1;

    // Initialize index by 1
    int ind = 1;

    // Loop to find K'th largest element
    for (auto it = st.begin(); ind <= N; it++) {

        // If sorted index is equal to k
        // return element of that index
        if (ind == (N - K + 1))
            return *it;

        // Increment the index by 1
        ind++;
    }
}

// Driver Code
int main()
{
    queue<int> q;

    // Pushing elements into queue
    q.push(15);
    q.push(27);
    q.push(18);
    q.push(13);

    int K = 2;

    // Call function and store return value
    // into kMaxx
    int kMaxx = kElement(q, K);

    // Print the Kth largest element
    cout << "The " << K << "th largest element is " << kMaxx
         << endl;

    return 0;
}
Output
The 2th largest element is 18

Time Complexity: O(N*logN), to insert all the elements into the set.
Auxiliary Space: O(N), to store all elements into the set.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK