Kth Largest Element Editorial

Practice Problem Link: Kth Largest Element | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a list of numbers, find the Kth largest element in the list.

Naive Approach

A simple solution is to sort the array and get the Kth largest element.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

int getKthLargestElement(vector<int> list, int k) {
   k = list.size() - k;
   sort (list.begin(), list.end());
   return list[k];
}

Java

class Solution {
   int getKthLargestElement(int[] list, int k) {
       k = list.length - k;
       Arrays.sort (list);
       return list[k];
   }
}

Optimal Approach

The basic idea to solve this problem efficiently is quite similar to the quicksort algorithm.

•  Like quicksort, the array can be partitioned into two parts while placing the pivoted element at its correct position.
• If the given index is larger than the index of the pivoted element then search for the element in the right half otherwise search in the left half.
• The process will be stopped as soon as the Kth largest element is found.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(log(n))

Implementation

C++

int makePartition (vector<int> &arr, int low, int high) {
   int pivot = arr[high];
   int currentIndx = low - 1;
   for (int i = low; i < high; i++) {
       if (arr[i] < pivot) {
           currentIndx++;
           int temp = arr[i];
           arr[i] = arr[currentIndx];
           arr[currentIndx] = temp;
       }
   }
   int temp = arr[high];
   arr[high] = arr[currentIndx + 1];
   arr[currentIndx + 1] = temp;
   return currentIndx + 1;
}
int quickSelect (vector<int> &arr, int low, int high, int k) {
   if (k > 0 && k <= high - low + 1) {
       int pivot = makePartition (arr, low, high);
       if (pivot - low == k - 1) {
           return arr[pivot];
       } else if (pivot - low < k - 1) {
           return quickSelect (arr, pivot + 1, high, k - pivot + low - 1);
       } else {
           return quickSelect (arr, low, pivot - 1, k);
       }
   }
   return - 1;
}
int getKthLargestElement(vector<int> list, int k) {
   int n = list.size();
   return quickSelect (list, 0, n - 1, n - k + 1);
}

Java

class Solution {
   int makePartition (int[] arr, int low, int high) {
       int pivot = arr[high];
       int currentIndx = low - 1;
       for (int i = low; i < high; i++) {
           if (arr[i] < pivot) {
               currentIndx++;
               int temp = arr[i];
               arr[i] = arr[currentIndx];
               arr[currentIndx] = temp;
           }
       }
       int temp = arr[high];
       arr[high] = arr[currentIndx + 1];
       arr[currentIndx + 1] = temp;
       return currentIndx + 1;
   }
   int quickSelect (int[] arr, int low, int high, int k) {
       if (k > 0 && k <= high - low + 1) {
           int pivot = makePartition(arr, low, high);
           if (pivot - low == k - 1) {
               return arr[pivot];
           }
           else if (pivot - low < k - 1) {
               return quickSelect (arr, pivot + 1, high, k - pivot + low - 1);
           }
           else {
               return quickSelect (arr, low, pivot - 1, k);
           }
       }
       return - 1;
   }
   int getKthLargestElement(int[] list, int k) {
       int n = list.length;
       return quickSelect (list, 0, n - 1, n - k + 1);
   }
}