Problem Statement: Kth Largest Element in an Array

Description:

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.
You must solve this problem using Selection Sort.
Some top tech companies that have asked the "Kth Largest Element in an Array" problem in their interviews

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output = 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output = 4

Constraints

• n == nums.length
• 1 <= k <= n <= 10^3.
• -10^2 <= nums[i] <= 10^2.

Output Format

Return a integer value

Now try it yourself
.
.
.
.
.
.
.
.
.
.
.
.
.

Solution in C:

#include<stdio.h>

int findKthLargest(int nums[], int k, int n){
  
      for(int i=0; i<n-1; i++){
            
           int min_idx = i;  // Let minimum or smallest number 
            
           for(int j=i+1; j<n; j++){
                if(nums[j] < nums[min_idx]){
                min_idx = j;
                }
           }
           int temp = nums[i];
           nums[i] = nums[min_idx];
           nums[min_idx] = temp;
      }

      return nums[n-k];
}

void main(){
   int nums[] = {3,2,1,5,6,4}; int n = 6;
   int k = 2;
   int answer = findKthLargest(nums, k, n);
}

Solution in JAVA:

class Solution{

    public int findKthLargest(int[] nums, int k){
        int n = nums.length;
        for(int i=0; i<n-1; i++){
            
            int min_idx = i;  // Let minimum or smallest number 
            
            for(int j=i+1; j<n; j++){
                if(nums[j] < nums[min_idx]){
                    min_idx = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[min_idx];
            nums[min_idx] = temp;
        }
        
        return nums[n-k];   // getting the answer
    }

    public static main(String[] args){
        int nums = {3,2,1,5,6,4};
        int k = 2;
        Solution solve = new Solution();
        int answer = solve.findKthLargest(nums, k);
    }
}

Solution in C++:

#include<bits/stdc++.h>
using namespace std;
int findKthLargest(int nums[],int n,int k){
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; 
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        swap(nums[minIndex], nums[i]);
    }
}
return nums[n-k];
}

int main(){
   int nums[]={3,2,1,5,6,4};
   int k=2;
   cout<<"The kth largest element is"<<endl;
   cout<<findKthLargest(nums,6,k);//where 6 is the size of array
}

Time Complexity: O(n^2)
Space Complexity: O(1)

Explanation

• Initializes an array nums with the values [3, 2, 1, 5, 6, 4] and the k with value 2 as example.

• Then calls the findKthLargest method with array nums and k as argument and stores the answer in the variable answer.

• The length of the array nums is stored in the variable n.

         for(int i = 0; i < n - 1; i++) {

• This loop iterates over the array from the first element to the second last element.

            int min_idx = i;  // Let minimum or smallest number
            for(int j = i + 1; j < n; j++) {
                if(nums[j] < nums[min_idx]) {
                    min_idx = j;
                }
            }

• The inner loop finds the smallest element in the unsorted portion of the array.

• The variable min_idx keeps track of the index of the smallest element found so far.

• If an element smaller than the current minimum is found, min_idx is updated.

• After finding the smallest element, the code swaps it with the element at the current position i.

        return nums[n - k];  // getting the answer

• After sorting the array, the kth largest element will be at the position n - k, the method returns it.

Follow Up Question: Can you reduce the time complexity of this function.
.
.
.
.
.
.
Hint : concept of FIFO(Priority Queue).
Try it Yourself..

Concept of Selection Sort Click here.
For more interview problems Click here.

Happy Coding!