Understanding Algorithm: Complexity and Performance

How to find the kth smallest/largest element in an array?

Board Infinity
Board Infinity
How to find the kth smallest/largest element in an array?

    A quick guide to Asymptotic Analysis

    Searching Algorithm and its Types

    What is Hashing in Data Structure?

    How to Build a TreeMap?

    Difference between Hashmap and HashTable

    A Quick Guide to Bubble Sort Algorithm

    How to find the kth smallest/largest element in an array?

    How to use Merge Sort with Linked Lists

    Finding Array Triplets with Given Sum

    What Is An Algorithm (Understanding The Ingredients)

    Tail Recursion Problem

    Stack vs Heap Memory: Key Differences

    Algorithm and Flowchart: Differences Explained

    Big O Notation: Space and Time Complexity

    Graphs in Data Structure and Algorithm

    Time Complexity: Explanation

    Binary Search Tree: Explanation

    Heap Sort Algorithm

    Time Complexity of Sorting Algorithms

    Load Factor and Rehashing

Overview

Given an unsorted array “arr”, find and print the “kth” smallest/largest element of the array.

Scope

  • The method of sorting the array.
  • The method of using a min-heap data structure.
  • The method of using a max-heap data structure.

By sorting the array

Concept

We can sort the given array “arr”, and then access the element with index k. After sorting, for any valid index of arr “i”, the ith smallest element gets stored at the index i.

Implementation

#include "iostream"

#include "vector"

#include "algorithm"


using namespace std;


int findKthSmallest(vector<int>&v, int k){

    sort(begin(v), end(v));

    return v[k - 1];

}


int main(){

    vector<int> arr = {10, 9, 1, 2, 5, 3, 4};

    int k = 3;

    cout << "The 3rd smallest element is : "<< findKthSmallest(arr, k)<<endl;

    return 0;

} 

write your code here: Coding Playground

Output

The 3rd smallest element is : 3

Using Min-Heap

Concept

Heap is also called a priority queue. It’s a data structure that stores elements in a sorted fashion. It provides access to only the top element in it viz the element with the highest priority. The order of the elements in a heap is determined by tier priority. But what is a priority?

It could be any parameter for the comparison of two data items of the same type. For example, the priority of two elements could be determined by checking which of them is larger, a string may have a higher priority over another if it is lexicographically smaller than the other, etc.

Implementation

In this method, we shall use a min-heap. It always stores the elements in an order such that the smallest element is always available at the top. We push all the elements from the array in the min-heap. Then we remove the top element from the heap repeatedly k-1 times. Therefore the kth element that is present at the top of the heap is also the kth smallest element.

#include "iostream"

#include "vector"

#include "queue"


using namespace std;


class cmp{

    public:

    bool operator()(const int&x, const int&y){

        return x>y;

    }

};


int findKthSmallest(vector<int>&v, int k){

    priority_queue<int, vector<int>, cmp>pq(begin(v), end(v));

    while(--k>0){

        pq.pop();

    }

    return pq.top();

}


int main(){

    vector<int> arr = {10, 9, 1, 2, 5, 3, 4};

    int k = 3;

    cout << "The 3rd smallest element is : "<< findKthSmallest(arr, k)<<endl;

    return 0;

}


write your code here: Coding Playground

Output

The 3rd smallest element is : 3

Using Max-Heap

Concept

The concept here is similar to that in the above. The difference here is that instead of a min-heap, we use a max-heap. We iterate over the elements of the array, for each of which:
* We push it into the heap.
* If the size of the heap exceeds k, we pop off the top element of the heap.

At the end of this process, the smallest k elements of the given array will be present in the heap. The top of the heap is the kth smallest element as required, which we shall return.

Implementation

#include "iostream"

#include "vector"

#include "queue"


using namespace std;


int findKthSmallest(vector<int>&v, int k){

    priority_queue<int>pq;

    for(int it:v){

        pq.push(it);

        if(pq.size()>k){

            pq.pop();

        }

    }

    return pq.top();

}


int main(){

    vector<int> arr = {10, 9, 1, 2, 5, 3, 4};

    int k = 3;

    cout << "The 3rd smallest element is: "<< findKthSmallest(arr, k)<<endl;

    return 0;

}

write your code here: Coding Playground

Output

The 3rd smallest element is : 3