Third greatest element

Easy
0/40
Average time to solve is 20m
15 upvotes
Asked in companies
OlaWalmartOracle

Problem statement

Given an array/list 'ARR' of ‘N’ distinct integers, you are supposed to find the third largest element in the given array 'ARR'.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line of each test case contains ‘N’ single space-separated distinct integers denoting the elements of 'ARR'.
Output Format : 
For each test case, print the third largest element in the given array/list 'ARR'.
Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
3 <= N <= 10^4
-10^5 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the i-th elements of the given array/list.

Time Limit: 1 sec
Sample Input 1 :
2
5
2 6 7 4 9
4
7 2 5 4
Sample Output 1 :
6
4
Explanation of Sample Input 1 :
In the first test case, if we arrange the array in non decreasing order we will get { 2, 4, 6, 7, 9}. Thus the third largest element is 6.

In the second test case, the third largest element is 4.
Sample Input 2 :
2
5
1 -4 2 5 3
3
3 5 6
Sample Output 2 :
2
3
Explanation of Sample Input 2 :
In the first test case, the third largest element is 2.

In the second test case, the third largest element is 3.
Hint

Can you think about sorting?

Approaches (3)
Sorting Based Approach

The idea is to sort the array in non-decreasing order, and then return the third element from the back of the array.

 

The steps are as follows :

  1. Sort the array in non-decreasing order.
  2. Return the third element from the back of the array.
Time Complexity

O( N * log(N) ), where ‘N’ is the number of elements in the given array/list.

 

We are sorting the array which will take O( N * log(N) ) time. Thus, the overall time complexity is O( N * log(N) ).

Space Complexity

O(1)

 

We are not using any extra space. Thus, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Third greatest element
Full screen
Console