Last Updated: 17 Jan, 2021
Third greatest element
Easy
Asked in companies
Given an array/list 'ARR' of ‘N’ distinct integers, you are supposed to find the third largest element in the given array 'ARR'.
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
Approaches
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 :
- Sort the array in non-decreasing order.
- Return the third element from the back of the array.
The idea is to iterate through the array and find the largest element and the second-largest elements in the given array/list and then again iterate to find the third largest element in the given array/list.
The steps are as follows :
- Let’s define three variables “MAXONE”, “MAXTWO”, “MAXTHREE” to store the largest, second largest, and the third-largest elements of the given array/list respectively.
- Iterate through the array and find the largest element and store it in “MAXONE”.
- Iterate through the array and find the largest element which is not equal to “MAXONE” and store it in “MAXTWO”.
- Iterate through the array and find the largest element which is not equal to “MAXONE” or “MAXTWO” and store it in “MAXTHREE”.
Return “MAXTHREE”.
The idea is to iterate through the array only once and keep track of the largest element, second largest, and the third-largest element simultaneously.
The steps are as follows :
- Let’s define three variables “MAXONE”, “MAXTWO”, “MAXTHREE” to store the largest, second-largest, and the third-largest elements of the given array/list respectively. Initialize, each of them to -ve infinity(i.e INT_MIN).
- Iterate through the array, let’s say our current index is ‘i’ and the current element is “ARR[i]”.
- If ARR[i] is greater than “MAXONE'' then update “MAXTHREE” to “MAXTWO” as the element which was second largest previously will now become the third-largest. Update “MAXTWO” to “MAXONE” as the element which was the largest previously will now become the second largest. Finally update “MAXONE” to ARR[i], as the largest element is ARR[i].
- Otherwise if ARR[i] is greater than “MAXTWO” then update “MAXTHREE” to “MAXTWO” as the element which was second largest previously will now become the third-largest. Update “MAXTWO” to ARR[i] as ARR[i] will now be the second-largest element.
- Else if ARR[i] is greater than “MAXTHREE” then update “MAXTHREE” to ARR[i] as ARR[i] will now be the third-largest element.
Return “MAXTHREE”.
Similar problems