Third Largest Element

Problem

Given an array of distinct elements. Find the third largest element in it.

Suppose you have A[] = 7, its output will be 5 because it is the 3 largest element in the array A.

Examples:

Example 1:

Input:
N = 5
A[] = {2,4,1,3,5}
Output: 3

Example 2:

Input:
N = 2
A[] = {10,2}
Output: -1

Your task:

Complete the function thirdLargest() which takes the array a[] and the size of the array, n, as input parameters and returns the third largest element in the array. It return -1 if there are less than 3 elements in the given array.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^5$
• $1<=A[i]<=10^5$

Solution

Python

def thirdLargest(self,a, n):
    if (n < 3):
        return -1
    else: 
        a = sorted(a)                 
        return a[-3]  

Java

int thirdLargest(int a[], int n) {
    if (n < 3) {
        return -1; 
    } 
    else {
        Arrays.sort(a);
        return a[n - 3];
    }
}

C++

int thirdLargest(int a[], int n) {
    if (n < 3) {
        return -1; 
    } 
    else {
        std::sort(a, a + n);
        return a[n - 3];
    }
}

C

int thirdLargest(int* a, int n) {
    if (n < 3) {
        return -1; 
    } 
    else {
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        return a[n - 3];
    }
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$