Third greatest element
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

Question

Third greatest element

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

Accepted Answer

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 :

Sort the array in non-decreasing order.
Return the third element from the back of the array.

Space Complexity: O(logn)Explanation:

O(1)

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

Time Complexity: O(nlogn)Explanation:

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) ).

Java (SE 1.8)

/*

    Time Complexity: O(N * log(N))

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    public static int findThirdLagrest(ArrayList < Integer > arr) {

        int n = arr.size();



        // Sort the array.

        Collections.sort(arr);



        // Return the 3rd element from the back.

        return arr.get(n - 3);

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N * log(N))

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

*/



#include 



int findThirdLagrest(vector < int > & arr) {

    int n = arr.size();



    // Sort the array.

    sort(arr.begin(), arr.end());



    // Return the 3rd element from the back.

    return arr[n - 3];

}

Accepted Answer

Multiple Traversals Approach

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”.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n)Explanation:

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

We are iterating through the given array/list 3 times which requires O(N) time. Thus, the overall time complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list.

'''



import sys



def findThirdLagrest(arr):

    

    # For storing largest,second largest and third largest elements.

    maxOne = -sys.maxsize

    maxTwo = -sys.maxsize

    maxThree = -sys.maxsize

    n = len(arr)



    # Iterate throught the array.

    for i in range(n):

        # Find the maximum element.

        if maxOne < arr[i]:

            maxOne = arr[i]

        

    # Iterate through the array.

    for i in range(n):

        # Find the second largest element.

        if (arr[i] != maxOne) and (maxTwo < arr[i]):

            maxTwo = arr[i]



    # Iterate through the array.

    for i in range(n):

        # Find the third largest element.

        if (arr[i] != maxOne) and (arr[i] != maxTwo) and (maxThree < arr[i]):

            maxThree = arr[i]

        

    return maxThree

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list.

*/



import java.util.ArrayList;



public class Solution {



    public static int findThirdLagrest(ArrayList < Integer > arr) {

        /* 

        	For storing largest,second largest 

        	and third largest elements.

        */

        

        int maxOne = Integer.MIN_VALUE, maxTwo = Integer.MIN_VALUE, maxThree = Integer.MIN_VALUE;



        int n = arr.size();



        // Iterate throught the array.

        for (int i = 0; i < n; i++) {

            // Find the maximum element.

            if (maxOne < arr.get(i)) {

                maxOne = arr.get(i);

            }

        }



        // Iterate through the array.

        for (int i = 0; i < n; i++) {

            // Find the second largest element.

            if (arr.get(i) != maxOne && maxTwo < arr.get(i)) {

                maxTwo = arr.get(i);

            }

        }



        // Iterate through the array.

        for (int i = 0; i < n; i++) {



            // Find the third largest element.

            if (arr.get(i) != maxOne && arr.get(i) != maxTwo && maxThree < arr.get(i)) {

                maxThree = arr.get(i);

            }

        }



        return maxThree;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list.

*/



#include 



int findThirdLagrest(vector < int > & arr) {

    // For storing largest,second largest and third largest elements.

    int maxOne = INT_MIN, maxTwo = INT_MIN, maxThree = INT_MIN;



    int n = arr.size();



    // Iterate throught the array.

    for (int i = 0; i < n; i++) {

        // Find the maximum element.

        if (maxOne < arr[i]) {

            maxOne = arr[i];

        }

    }



    // Iterate through the array.

    for (int i = 0; i < n; i++) {

        // Find the second largest element.

        if (arr[i] != maxOne && maxTwo < arr[i]) {

            maxTwo = arr[i];

        }

    }



    // Iterate through the array.

    for (int i = 0; i < n; i++) {

        // Find the third largest element.

        if (arr[i] != maxOne && arr[i] != maxTwo && maxThree < arr[i]) {

            maxThree = arr[i];

        }

    }



    return maxThree;

}

Accepted Answer

Single Traversal Approach

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”.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n)Explanation:

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

We are iterating through the given array/list which requires O(N) time. Thus, the overall time complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

'''



import sys



def findThirdLagrest(arr):

    # For storing largest,second largest and third largest elements.

    maxOne = -sys.maxsize

    maxTwo = -sys.maxsize

    maxThree = -sys.maxsize



    n = len(arr)



    # Iterate through the array.

    for i in range(n): 

        # Update the elements.

        if maxOne < arr[i]:

            maxThree = maxTwo

            maxTwo = maxOne

            maxOne = arr[i]

        elif maxTwo < arr[i]:

            maxThree = maxTwo

            maxTwo = arr[i]

        elif maxThree < arr[i]:

            maxThree = arr[i]

        

    return maxThree

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

*/



#include 



int findThirdLagrest(vector < int > & arr) {

    // For storing largest,second largest and third largest elements.

    int maxOne = INT_MIN, maxTwo = INT_MIN, maxThree = INT_MIN;



    int n = arr.size();



    // Iterate through the array.

    for (int i = 0; i < n; i++) {

        // Update the elements.

        if (maxOne < arr[i]) {

            maxThree = maxTwo;

            maxTwo = maxOne;

            maxOne = arr[i];

        } else if (maxTwo < arr[i]) {

            maxThree = maxTwo;

            maxTwo = arr[i];

        } else if (maxThree < arr[i]) {

            maxThree = arr[i];

        }

    }



    return maxThree;

}

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the given array/list

*/



import java.util.ArrayList;



public class Solution 

{

    

    public static int findThirdLagrest(ArrayList arr) 

    {

        /*

        	For storing largest,second largest 

            and third largest elements.

        */

        

        int maxOne = Integer.MIN_VALUE, maxTwo = Integer.MIN_VALUE, maxThree = Integer.MIN_VALUE;



        int n = arr.size();



        // Iterate through the array.

        for (int i = 0; i < n; i++) 

        {

            

            // Update the elements.

            if (maxOne < arr.get(i)) 

            {

                maxThree = maxTwo;

                maxTwo = maxOne;

                maxOne = arr.get(i);

            } 

            else if (maxTwo < arr.get(i)) 

            {

                maxThree = maxTwo;

                maxTwo = arr.get(i);

            } 

            else if (maxThree < arr.get(i)) 

            {

                maxThree = arr.get(i);

            }

        }



        return maxThree;

    }

}

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 :

Output Format :

Note :

Constraints :

Top Freshworks Software Developer interview questions & answers

Popular interview questions of Software Developer