Thread: Find 6th largest element in an array

Find 6th largest element in an integer array.

Code:

int sixthLargest(const int a[]) {
    int max[6] = {INT_MIN};
    for (int i = 0; i < N; ++i)
        if (a[i] > max[0]) max[0] = a[i];
    for (int x = 1; x < 6; ++x)
        for (int i = 0; i < N; ++i)
            if (a[i] > max[x] && a[i] < max[x - 1]) max[x] = a[i];
    return max[5];
}

T: O(6n) = O(n)
S: O(6) = O(1)

@surfer
The solution which you provide is brute force and the analysis is also flawed. Do the analysis based on fact that find the kth largest element. Now the analysis will yield O(k*n) which is actually considered O(n^2) since 1<=k<=n . Thus, your solution is O(n^2)
For O(n) solution, visit Selection algorithm - Wikipedia, the free encyclopedia

Avi
Avi Dullu&#039;s Code Arena

1. build heap of first 6 element
2. if new element if greater than root element of min Heap, Delete root and insert new element and maintain heap

Arr[n] //given array
arr[6] = {0};
arr[0] = Arr[0];
i = 0;
for(j=1; j<n; j++)
{
if(arr[i] < Arr[j])
{
i = (i + 1)%6;
arr[i] = Arr[j];
}
}
i = (i +1)% 6;
printf("6 th largest = %d",arr[i]);