Problem Statement: Given an unsorted array, print Kth Largest and Smallest Element from an unsorted array.
Examples:
Example 1: Input: Array = [1,2,6,4,5,3] , K = 3 Output: kth largest element = 4, kth smallest element = 3 Example 2: Input: Array = [1,2,6,4,5] , k = 3 Output : kth largest element = 4, kth smallest element = 4
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Sorting the Array
- The most naive approach is to sort the given array in descending order.
- The index of kth Largest element = k-1 ( zero-based indexing )
- The index of kth Smallest element = n-k
- The array can also be sorted in ascending order.
- The index of kth Largest element = n-k
- The index of kth Smallest element = k-1 ( zero based indexing )
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std ;
class Solution {
public:
void kth_Largest_And_Smallest_By_AscendingOrder(vector<int>&arr, int k) {
sort(arr.begin(), arr.end()) ;
int n = arr.size() ;
cout << "kth Largest element " << arr[n - k] << ", " <<
"kth Smallest element " << arr[k - 1];
}
} ;
int main() {
vector<int>arr = {1, 2, 6, 4, 5, 3} ;
Solution obj ;
obj.kth_Largest_And_Smallest_By_AscendingOrder(arr, 3) ;
return 0 ;
}
Output: kth Largest element 4, kth Smallest element 3
Time complexity: O(nlogn)
Space complexity: O(1)
Java Code
import java.util.*;
class Solution {
static void kth_Largest_And_Smallest_By_AscendingOrder(int[] arr, int k) {
Arrays.sort(arr);
int n = arr.length;
System.out.println("kth Largest element "+arr[n - k]+", "+
"kth Smallest element "+arr[k - 1]);
}
public static void main(String args[]) {
int arr[] = {1, 2, 6, 4, 5, 3} ;
kth_Largest_And_Smallest_By_AscendingOrder(arr, 3) ;
}
}
Output: kth Largest element 4, kth Smallest element 3
Time complexity: O(nlogn)
Space complexity: O(1)
Python Code
from typing import List
class Solution:
def kth_Largest_And_Smallest_By_AscendingOrder(self, arr: List[int], k: int) -> None:
arr.sort()
n = len(arr)
print(
f"kth Largest element {arr[n - k]}, kth Smallest element {arr[k - 1]}")
if __name__ == "__main__":
arr = [1, 2, 6, 4, 5, 3]
Solution().kth_Largest_And_Smallest_By_AscendingOrder(arr, 3)Output: kth Largest element 4, kth Smallest element 3
Time complexity: O(nlogn)
Space complexity: O(1)
Solution 2: Using Heap
- The idea is to construct a max-heap of elements. Since the top element of the max heap is the largest element of the heap, we will remove the top K-1 elements from the heap. The top element will be Kth’s Largest element.
- To get the Kth Smallest element, we will use a min-heap. After the removal of the top k-1 elements, the Kth Smallest element is top of the Priority queue.
Let the array be [17,7,2,30,21] and k = 3
Similarly, for the smallest kth element we will be using Min-Heap. After, extracting the top k-1 values will be having Kth Smallest element.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std ;
class Solution {
public:
void kth_Largest_MaxHeap(vector<int>&arr, int k) {
priority_queue<int>pq ;
int n = arr.size() ;
for (int i = 0; i < arr.size(); i++) {
pq.push(arr[i]) ;
}
int f = k - 1 ;
while (f > 0) {
pq.pop() ;
f-- ;
}
cout << "Kth Largest element " << pq.top() << "\n" ;
}
void kth_Smallest_MinHeap(vector<int>&arr, int k) {
priority_queue<int, vector<int>, greater<int>>pq ;
int n = arr.size() ;
for (int i = 0; i < arr.size(); i++) {
pq.push(arr[i]) ;
}
int f = k - 1 ;
while (f > 0) {
pq.pop() ;
f-- ;
}
cout << "Kth Smallest element " << pq.top() << "\n" ;
}
} ;
int main() {
vector<int>arr = {1, 2, 6, 4, 5, 3} ;
Solution obj ;
obj.kth_Largest_MaxHeap(arr, 3) ;
obj.kth_Smallest_MinHeap(arr, 3) ;
return 0 ;
}
Output:
Kth Largest element 4
Kth Smallest element 3
Time complexity: O(k+(n-k)*log(k)) , n = size of array
Space complexity: O(k)
Java Code
import java.util.*;
class Solution {
static void kth_Largest_MaxHeap(int[] arr, int k) {
PriorityQueue<Integer>pq= new PriorityQueue<>((a,b)->b-a);
int n = arr.length ;
for (int i = 0; i < arr.length; i++) {
pq.add(arr[i]) ;
}
int f = k - 1 ;
while (f > 0) {
pq.remove() ;
f-- ;
}
System.out.println("Kth Largest element "+pq.peek()) ;
}
static void kth_Smallest_MinHeap(int[] arr, int k) {
PriorityQueue<Integer>pq= new PriorityQueue<>();
int n = arr.length ;
for (int i = 0; i < n; i++) {
pq.add(arr[i]) ;
}
int f = k - 1 ;
while (f > 0) {
pq.remove() ;
f-- ;
}
System.out.println("Kth Smallest element "+pq.peek()) ;
}
public static void main(String args[]) {
int arr[] = {1, 2, 6, 4, 5, 3} ;
kth_Largest_MaxHeap(arr, 3) ;
kth_Smallest_MinHeap(arr, 3) ;
}
}
Output:
Kth Largest element 4
Kth Smallest element 3
Time complexity: O(k+(n-k)*log(k)) , n = size of array
Space complexity: O(k)
Python Code
import heapq
class Solution:
def kth_Largest_MaxHeap(self, arr, k):
pq = []
n = len(arr)
for i in range(n):
heapq.heappush(pq, -arr[i])
f = k - 1
while f > 0:
heapq.heappop(pq)
f -= 1
print("Kth Largest element", -pq[0])
def kth_Smallest_MinHeap(self, arr, k):
pq = []
n = len(arr)
for i in range(n):
heapq.heappush(pq, arr[i])
f = k - 1
while f > 0:
heapq.heappop(pq)
f -= 1
print("Kth Smallest element", pq[0])
if __name__ == "__main__":
arr = [1, 2, 6, 4, 5, 3]
obj = Solution()
obj.kth_Largest_MaxHeap(arr, 3)
obj.kth_Smallest_MinHeap(arr, 3)Output:
Kth Largest element 4
Kth Smallest element 3
Time complexity: O(k+(n-k)*log(k)) , n = size of array
Space complexity: O(k)
Solution 3: Using Quickselect Algorithm
- Choose any random element as PIVOT.
- Use Partition Algorithm to partition the given array into 2 parts and place the PIVOT at its correct position ( called as index ).
- Partition Algorithm: All the elements are compared to the PIVOT, and the elements less than the PIVOT are shifted toward the left side of the array and greater ones are shifted toward the right side of the array.
- Now since all elements right to the PIVOT are greater and left to the PIVOT are smaller, compare the index with N-k ( where N = size of the array ) and recursively find the part to find the Kth largest element.
- The worst-case time complexity of this method is O(n^2) but its Average time complexity is O(n).
Code for kth largest element:
C++ Code
#include <bits/stdc++.h>
using namespace std ;
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[left] ;
int l = left + 1 ;
int r = right;
while (l <= r) {
if (arr[l] < pivot && arr[r] > pivot) {
swap(arr[l], arr[r]);
l++ ;
r-- ;
}
if (arr[l] >= pivot) {
l++;
}
if (arr[r] <= pivot) {
r--;
}
}
swap(arr[left], arr[r]);
return r;
}
int kth_Largest_Element(vector<int>& arr, int k) {
int left = 0, right = arr.size() - 1, kth;
while (1) {
int idx = partition(arr, left, right);
if (idx == k - 1) {
kth = arr[idx];
break;
}
if (idx < k - 1) {
left = idx + 1;
} else {
right = idx - 1;
}
}
return kth;
}
int main() {
vector<int>arr ;
arr.push_back(12) ;
arr.push_back(3) ;
arr.push_back(5) ;
arr.push_back(7) ;
arr.push_back(4) ;
arr.push_back(19) ;
arr.push_back(26) ;
int n = arr.size(), k = 1;
cout << "Kth Largest element is " << kth_Largest_Element(arr, k);
return 0 ;
}
Output: Kth Largest element is 26
Time complexity: O(n) , where n = size of the array
Space complexity: O(1)
Java Code
import java.util.*;
class TUF{
static int partition(int[] arr, int left, int right) {
int pivot = arr[left] ;
int l = left + 1 ;
int r = right;
while (l <= r) {
if (arr[l] < pivot && arr[r] > pivot) {
int temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
l++ ;
r-- ;
}
if (arr[l] >= pivot) {
l++;
}
if (arr[r] <= pivot) {
r--;
}
}
int temp2=arr[left];
arr[left]=arr[r];
arr[r]=temp2;
return r;
}
static int kth_Largest_Element(int[] arr, int k) {
int left = 0, right = arr.length - 1, kth;
while (true) {
int idx = partition(arr, left, right);
if (idx == k - 1) {
kth = arr[idx];
break;
}
if (idx < k - 1) {
left = idx + 1;
} else {
right = idx - 1;
}
}
return kth;
}
public static void main(String args[]) {
int arr[]={12,3,5,7,4,19,26};
int n = arr.length, k = 1;
System.out.println("Kth Largest element is "+kth_Largest_Element(arr, k));
}
}
Output: Kth Largest element is 26
Time complexity: O(n) , where n = size of the array
Space complexity: O(1)
Python Code
from typing import List
def partition(arr: List[int], left: int, right: int) -> int:
pivot = arr[left]
l = left + 1
r = right
while l <= r:
if arr[l] < pivot and arr[r] > pivot:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
if arr[l] >= pivot:
l += 1
if arr[r] <= pivot:
r -= 1
arr[left], arr[r] = arr[r], arr[left]
return r
def kth_Largest_Element(arr: List[int], k: int) -> int:
left = 0
right = len(arr) - 1
kth = 0
while 1:
idx = partition(arr, left, right)
if idx == k - 1:
kth = arr[idx]
break
if idx < k - 1:
left = idx + 1
else:
right = idx - 1
return kth
if __name__ == "__main__":
arr = [12, 3, 5, 7, 4, 19, 26]
n = len(arr)
k = 1
print(f"Kth Largest element is {kth_Largest_Element(arr, k)}")Output: Kth Largest element is 26
Time complexity: O(n) , where n = size of the array
Space complexity: O(1)
code for Kth Smallest element:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int partition(vector<int>&arr, int l, int r)
{
int f = arr[r] ;
int i = l;
for (int j = l; j <= r - 1; j++) {
if (arr[j] <= f) {
swap(arr[i], arr[j]) ;
i++;
}
}
swap(arr[i], arr[r]);
return i;
}
int kth_Smallest_Element(vector<int>&arr, int l, int r, int k)
{
if (k <= r - l + 1 && k > 0) {
int ind = partition(arr, l, r);
if (ind - l == k - 1) {
return arr[ind];
}
if (ind - l > k - 1) {
return kth_Smallest_Element(arr, l, ind - 1, k);
}
return kth_Smallest_Element(arr, ind + 1, r, k - ind + l - 1);
}
return INT_MAX;
}
int main()
{
vector<int>arr ;
arr.push_back(12) ;
arr.push_back(3) ;
arr.push_back(5) ;
arr.push_back(7) ;
arr.push_back(4) ;
arr.push_back(19) ;
arr.push_back(26) ;
int n = arr.size(), k = 1;
cout << "Kth smallest element is " << kth_Smallest_Element(arr, 0, n - 1, k);
return 0;
}
Output: Kth smallest element is 3
Time complexity: O(n) ,where n = size of the array
Space complexity: O(1)
Java Code
import java.util.*;
class TUF{
static int partition(int[] arr, int l, int r) {
int f = arr[r] ;
int i = l;
for (int j = l; j <= r - 1; j++) {
if (arr[j] <= f) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;
}
}
int temp=arr[i];
arr[i]=arr[r];
arr[r]=temp;
return i;
}
static int kth_Smallest_Element(int[] arr,int l,int r, int k) {
if (k <= r - l + 1 && k > 0) {
int ind = partition(arr, l, r);
if (ind - l == k - 1) {
return arr[ind];
}
if (ind - l > k - 1) {
return kth_Smallest_Element(arr, l, ind - 1, k);
}
return kth_Smallest_Element(arr, ind + 1, r, k - ind + l - 1);
}
return Integer.MAX_VALUE;
}
public static void main(String args[]) {
int arr[]={12,3,5,7,4,19,26};
int n = arr.length, k = 1;
System.out.println("Kth Smallest element is "+kth_Smallest_Element(arr, 0,n-1,k));
}
}
Output: Kth smallest element is 3
Time complexity: O(n) ,where n = size of the array
Space complexity: O(1)
Python Code
from typing import List
def partition(arr: List[int], l: int, r: int) -> int:
f = arr[r]
i = l
for j in range(l, r):
if arr[j] <= f:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[r] = arr[r], arr[i]
return i
def kth_Smallest_Element(arr: List[int], l: int, r: int, k: int) -> int:
if k <= r - l + 1 and k > 0:
ind = partition(arr, l, r)
if ind - l == k - 1:
return arr[ind]
if ind - l > k - 1:
return kth_Smallest_Element(arr, l, ind - 1, k)
return kth_Smallest_Element(arr, ind + 1, r, k - ind + l - 1)
return float("inf")
if __name__ == "__main__":
arr = [12, 3, 5, 7, 4, 19, 26]
n = len(arr)
k = 1
print(f"Kth smallest element is {kth_Smallest_Element(arr, 0, n - 1, k)}")Output: Kth smallest element is 3
Time complexity: O(n) ,where n = size of the array
Space complexity: O(1)
Special thanks to Shreyas Vishwakarma and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article