K’th Largest Element in an array

Ranjul Arumadi
Last Updated: May 13, 2022
Difficulty Level :
EASY

Introduction

Operations on arrays is an important area to master when it comes to programming. Finding the k’th largest element in an array is one such frequently asked coding question in coding interviews. You can practise the question at the CodeStudio and return to this blog if you feel stuck. 

Understanding the problem

The given task is to find the K’th largest element in an array. Here we must note that the question is one level higher compared to finding the largest or the smallest element in an array. In this task, ‘K’ refers to the cardinality of array values.

For example, consider the array below: 

Arr[4] = {12, 34, 56, 2}

 

Here the largest element is 56, and the smallest element is 2.

The second largest element is 12, the third-largest element is 34 etc.

That clears about the ‘K’ value in the question. In this question, we assume that we are given an unsorted array having distinct elements.

Brute Force Approach: Sorting the array using bubble sort

This approach is the simplest one, and it involves using a sorting algorithm to sort the unsorted array. Bubble sort is one of the simplest sorting algorithms, and you can solve this question using this simple sorting method. If we sort the array in increasing order, the largest value will occupy the 0th index in the array. Similarly, the second largest value will be in the 1st index, the third largest element in the 2nd index, etc. Here we must note that we should print the k+1th array value while printing the Kth largest value as the array index starts from 0.

The code for the above-described method is given below.

Using bubble sort to sort the values in increasing order.

Implementation in C++

#include <stdio.h>

int main()
{
    int size, i, j, k, temp;

    printf("\nEnter size of array: ");
    scanf("%d", &size);

    // creating an array of size specified by user
    int arr[size];
    printf("\nEnter array values: ");
    for (i = 0; i < size; i++)
    {
        scanf("%d", &arr[i]);
    }

    printf("\nEnter k value: ");
    scanf("%d", &k);

    // Sorting in increasing order using bubble sort
    for (i = 0; i < size; i++)
    {
        for (j = 0; j < size; j++)
        {
            if (arr[i] < arr[j])
            {
                // swap arr[i] and arr[j]
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    printf("\nSorted array is: ");
    // display output
    for (i = 0; i < size; i++)
    {
        printf("%d\t", arr[i]);
    }

    // display the Kth largest value
    printf("\n\n%d'th largest value is %d", k, arr[k - 1]); // k-1 because array index starts from 0
    return 0;
}

Implementation in Java

Import java.util,*;
Import java.io.*;

public static void main (String[] args) throws java.lang.Exception {
		try {
			Scanner fs = new Scanner(System.in);
			
			int t = 1;
			//t = fs.nextInt();
			while(t-->0) {
				System.out.println("ENTER SIZE OF ARRAY");
				int size = fs.nextInt();
				
				 //creating an array of size specified by user

				int arr[] = new int[size];
				System.out.println("ENTER ARRAY VALUES");
				for(int i=0;i<size;i++) {
					arr[i] = fs.nextInt();
				}
				System.out.println("ENTER K VALUE");
				int k = fs.nextInt();
				int temp = 0;
				int i=0,j=0;
				
				 //Sorting in increasing order using bubble sort
				for(i=0;i<size;i++){
			        for(j=0;j<size;j++){
			            if(arr[i]<arr[j]){
			                //swap arr[i] and arr[j]
			                temp=arr[i];
			                arr[i]=arr[j];
			                arr[j]=temp;
			            }
			        }
			    }
				System.out.println("SORTED ARRAY IS -->");
				for(int a : arr) {
					System.out.print(a+" ");
				}
				System.out.println();
				  //display the Kth largest value

				System.out.println("THE Kth Largest Value is " + arr[k-1]);
				
			}	
		}
		
		catch (Exception e)
		{
			return;
		}
	}

Implementation in Python

size = 0
i= 0
j = 0
k = 0
temp = 0
print("enter array size")
size = int(input())
#creating an array of size specified by user
Arr = [] 
print("enter array values")
for i in range(size):
    x = int(input())
    Arr.append(x)    
print("enter k value")
k = int(input())
#Sorting in increasing order using bubble sort
for i in range(size):
    for j in range(size):
         if(Arr[i]<Arr[j]):
             #swap arr[i] and arr[j]
             Arr[i],Arr[j] = Arr[j],Arr[i]
print("sorted array is:")
#display output
for i in range(size):
       print(Arr[i],end = " ")
#display the Kth largest value
print( kth + "largest value is" + str(Arr[k-1]))

 

Input:

Enter the size of the array: 5
Enter array values: 1 0 34 5 76
Enter k value: 3

 

Output:

The sorted array is: 76     34      5       1       0
3'th largest value is 5

 

We can also sort the array in decreasing order. Then the K’th largest value will be arr[size-k], and K’th smallest value will be arr[k-1], where ‘size’  is the size of the array.

Further, this approach can be improved by using better sorting algorithms like Merge sort or Heap sort, which has lower time complexity than the bubble sort. 

Efficient Approaches

Optimised Quicksort

We understand from method one that sorting is the most basic and straightforward approach to solving this problem. Suppose we had used Quicksort rather than bubble sort, then there is a scope for optimisation. The optimisation works by not doing a complete Quicksort but to stop when the pivot element found while sorting itself is the 

Implementation in C++

#include <stdio.h>

int partition(int arr[], int start, int end)
{
    int i = start, j, x = arr[end], temp;
    for (j = start; j <= end - 1; j++)
    {
        if (arr[j] <= x)
        {
            // swap arr[i] and arr[j]
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    // swap arr[i] and arr[j]
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    return i;
}

int findingKthSmallest(int arr[], int start, int end, int k)
{
    // Checking if user input(k) falls within the indexes in the array.
    // Example if indexes are : 0 1 2 3, k can have values: 1,2,3,4 (4 = 3-0+1)
    if (k > 0 && k <= end - start + 1)
    {
        // Partition the array around last element and get
        // position of pivot element in sorted array
        int position = partition(arr, start, end);
        // If position value is same as k
        if (position - start == k - 1)
            return arr[position];
        // If position value is more, recur for left subarray
        if (position - start > k - 1)
            return findingKthSmallest(arr, start, position - 1, k);
        // Else recur for right subarray
        return findingKthSmallest(arr, position + 1, end, k - position + start - 1);
    }
    // If k is more than number of elements in array
    return -1;
}

int main()
{
    int size, i, j, k, temp, answer;
    printf("\nEnter size of array: ");
    scanf("%d", &size);
    // creating an array of size specified by user
    int arr[size];
    printf("\nEnter array values: ");
    for (i = 0; i < size; i++)
    {
        scanf("%d", &arr[i]);
    }
    printf("\nEnter k value: ");
    scanf("%d", &k);
    // arguments passed: input array, start index, end index, k value
    answer = findingKthSmallest(arr, 0, size - 1, k);
    printf("\n%dth largest value is %d", k, answer);
    return 0;
}

Implementation in Java

public static int partition(int a[], int start, int end) {
    int pivot = a[end]; // pivot element  
    int i = (start - 1);

    for (int j = start; j <= end - 1; j++) {
        // If current element is smaller than the pivot  
        if (a[j] < pivot) {
            i++; // increment index of smaller element  
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    int t = a[i + 1];
    a[i + 1] = a[end];
    a[end] = t;
    return (i + 1);
}

int findingKthSmallest(int arr[], int start, int end, int k) {
    // Checking if user input(k) falls within the indexes in the array.
    // Example if indexes are : 0 1 2 3, k can have values: 1,2,3,4 (4 = 3-0+1)

    if (k > 0 && k <= end - start + 1) {
        // Partition the array around last element and get
        // position of pivot element in sorted array
        int position = partition(arr, start, end);

        // If position value is same as k
        if (position - start == k - 1)
            return arr[position];
        // If position value is more, recur for left subarray
        if (position - start > k - 1)
            return findingKthSmallest(arr, start, position - 1, k);

        // Else recur for right subarray
        return findingKthSmallest(arr, position + 1, end, k - position + start - 1);
    }

    // If k is more than number of elements in array
    return -1;
}

Implementation in Python

size = 0
i= 0
j = 0
k = 0
temp = 0

print("enter array size")
size = int(input())

#creating an array of size specified by user
Arr = [] 
print("enter array values")
for i in range(size):
    x = int(input())
    Arr.append(x)    

print("enter k value")
k = int(input())

#Sorting in increasing order using bubble sort
for i in range(size):
    for j in range(size):
         if(Arr[i]<Arr[j]):
             #swap arr[i] and arr[j]
             Arr[i],Arr[j] = Arr[j],Arr[i]
print("sorted array is:")
#display output
for i in range(size):
       print(Arr[i],end = " ")

#display the Kth largest value
print( kth + "largest value is" + str(Arr[k-1]))

 

This is an optimization over method 1 if QuickSort is used as a sorting algorithm in the first step. In QuickSort, we pick a pivot element, move it to its correct position, and partition the surrounding array. The idea is, not to do complete Quicksort but stop at the point where the pivot itself is k’th smallest element. Also, not to recur for both left and right sides of the pivot, but recur for one of them according to the position of the pivot. The worst-case time complexity of this method is O(n2), but it works in O(n) on average. 

Using Max Heap

We can use a heap data structure to find the kth largest element. Max heap or min-heap can be used for this purpose. 

 

The steps can be outlined as:

  1. Build a Max heap tree. The time complexity for this operation is O(n).
  2. Extract the max value k times to get the kth largest element as the root of the heap.

 

Explanation:

A max-heap is a binary tree data structure. In this tree, the value of each node is greater than or equal to the values of the child of that node. In this tree, if a node is stored at index k, then the left child of that node will be at position 2k+1, and the right child will be at position 2k+2. 

 

Example: If the array name is Arr[] then-

  1. Parent node = Arr[(i-1)/2]
  2. Left child node = Arr[(2*i)+1]
  3. Right child node = Arr[(2*i)+2]

Implementation In Java

public static int partition(int a[], int start, int end) {
    int pivot = a[end]; // pivot element  
    int i = (start - 1);
    for (int j = start; j <= end - 1; j++) {
        // If current element is smaller than the pivot  
        if (a[j] < pivot) {
            i++; // increment index of smaller element  
            int t = a[i];
            a[i] = a[j];
            a[j] = t;

        }
    }
    int t = a[i + 1];
    a[i + 1] = a[end];
    a[end] = t;
    return (i + 1);
}
int findingKthSmallest(int arr[], int start, int end, int k) {
    // Checking if user input(k) falls within the indexes in the array.
    // Example if indexes are : 0 1 2 3, k can have values: 1,2,3,4 (4 = 3-0+1)
    if (k > 0 && k <= end - start + 1) {
        // Partition the array around last element and get
        // position of pivot element in sorted array
        int position = partition(arr, start, end);
        // If position value is same as k
        if (position - start == k - 1)
            return arr[position];
        // If position value is more, recur for left subarray
        if (position - start > k - 1)
            return findingKthSmallest(arr, start, position - 1, k);
        // Else recur for right subarray
        return findingKthSmallest(arr, position + 1, end, k - position + start - 1);
    }
    // If k is more than number of elements in array
    return -1;

}

Implementation in Python

#Implementing max-heap using heapq in python
import heapq

class MaxHeap:
    def __init__(self):
        self.data = []

    def top(self):
        return -self.data[0]

    def push(self, val):
        heapq.heappush(self.data, -val)

    def pop(self):
        return -heapq.heappop(self.data)    
        
max_heap = MaxHeap()

#here we are inserting 5 values into the heap
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
max_heap.push(9)
max_heap.push(6)

#setting k=3, to get the third largest element

k=3

#popping the root value for k-1 times to get the kth largest value
while k-1>0:
    max_heap.pop()
    k-=1
    
print(max_heap.top()) 

 

Output:

5

Using min-heap

This method follows the same logic and procedure as that in the previous method(using max heap). The only difference is that we use a min-heap over a max heap. In a min-heap, the parent or root node is usually lesser in value than the children nodes.

Frequently Asked Questions

What is the time complexity of using merge sort to sort an array?

The time complexity of Merge Sort is O(n*log n) in all the 3 cases (worst, average and best).
 

How are finding the K'th largest and smallest elements in an array different from one another?

If you can find the k’th largest element, then finding the K’th smallest element will be easy as only slight modifications have to be done in the code. This can be understood by just examining the solution method involving sorting the array discussed in the blog.
 

What are the different strategies discussed to find K'th largest/smallest elements in an array?

Some of the strategies discussed in the blog to find the K’th largest element in an array are by sorting the array and using the heap data structure.
 

What are some pre-requisite assumptions that are considered for the problem?

The prerequisite is that basic knowledge and basic experience working with arrays. The assumption that we have taken is that the given array is unsorted, and the elements of the array are unique. 
 

What are the best case time and space complexities that we can achieve for finding K'th largest/smallest element in an array?

The best time complexity can be achieved using heap data structures. It will be O(log N). Since Heapify is a recursive function, its space complexity is O(log N).

Conclusion

Finding Kth largest element in an array is an important interview question. The simplest solution involves sorting the array using a simple sorting algorithm like bubble sort. You can move on to other methods like using heap data structures to find the kth largest element in an array. 

If you want to test your understanding of this question, you can try to solve this question using CodeStudio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think