Home Arrays Kth largest element in an array (Method 1)

# Kth largest element in an array (Method 1)

Question: Given an unsorted array of integers and a number ‘k’. Return the kth largest element in the array.
Input: arr = {3,2,1,5,6,4}, k = 2
Output: 5

Given an unsorted array of integers, you need to determine the kth largest element. By taking a first glance at the problem we can be sure of one thing. If the array is already sorted in ascending order, we can simply return the element at arr[size – k]. This would give us the kth largest element. This is because the 2nd largest element is the largest element in the array and will exist at arr[size-2]. Since, the array starts at 0.

Let us start solving this problem with one of the most naive methods. By sorting the array. We can use any of the sorting methods we have discussed till now. QuickSort performs the fastest and hence we shall use it.

Once the array is sorted simply return the (size – k)th element.

.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
.hljs > mark.shcb-loc { background-color: #ddf6ff; }#include<stdio.h>

void swap(int *i, int *j)
{
int temp = *i;
*i = *j;
*j = temp;
}

int partition(int arr[], int start, int end)
{
int pivot = arr[end];
int i = start;
int j = end-1;
while(i <= j)
{
while(arr[i] < pivot) i++; while(arr[j] > pivot)
j--;
if(i <= j)
{
swap(&arr[i], &arr[j]);
i++;
j--;
}
}

swap(&arr[i], &arr[end]);
return i;
}

void performQuickSort(int arr[], int start, int end)
{
if(start < end)
{
int p = partition(arr, start, end);
performQuickSort(arr, start, p-1);
performQuickSort(arr, p+1, end);
}
}

void quickSort(int arr[], int size)
{
performQuickSort(arr, 0, size-1);
}

// driver program
int main(void)
{
int i;
int arr = {2, 6, 4, 10, 8, 1, 9, 5, 3, 7};

quickSort(arr,10);

printf("The 5th largest number in array is:-  %d", arr[10 - 5]);
return 0;
}
Code language: C++ (cpp)

A working implementation of the code can be found at this location. http://ideone.com/AXvFAq

Note that this is a very naive approach.
Time Complexity:- O(n log(n))
Space Complexity:- O(n)

#### You may also like July 2, 2017 - 03:26

I need more explanation. Thanks July 2, 2017 - 23:21

Which part are you facing a problem with? In a nutshell, we are sorting the array and finding the kth number. December 1, 2016 - 22:30

What if array has repeating elements.. December 2, 2016 - 14:02

The repeating elements should not be a problem. For example you have an array like {2, 2, 2, 2, 2}. The largest number is 2, smallest is 2 and the kth smallest number is also 2.
So if you have any array like {1,2,2,3,4,5,5,6,7,8}
The 4th and 5th largest element will be 5. October 31, 2016 - 02:24

Great question!! Keep up.

Looks like there is a typo – “… largest element in the array and will exist at arr[size].”
Shouldn’t it be arr[size-1] ? October 31, 2016 - 04:52

Thanks for pointing that out. I have corrected it.