Fourth Largest Element in the Array

Easy

0/40

Average time to solve is 20m

Contributed by

23 upvotes

Asked in companies

Problem statement

You are given an array consisting of 'N' integers. You have to find the fourth largest element present in the array.

If there is no such number present in the array, then print the minimum value of an integer which is -2147483648.

Follow Up:

Try solving this problem in O(N) time complexity.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains the integer 'N' representing the size of the array.

The second line of input contains N space-separated integers representing the array elements.

Output Format:

The only output line contains the fourth-largest element if present, otherwise print -2147483648

Note:

You are not required to explicitly print the output, it has already been taken care of. Just implement the function.

Constraints :

1 <= N < 10^6
-10^6 <= element <= 10^6

Time Limit: 1 sec

Sample Input 1:

5
3 5 1 3 1

Sample Output 1:

Explanation Of Sample Input 1:

5 is the largest element, 3 is the second-largest element, again we have a 3 so it's the third largest and 1 is the fourth-largest, hence the answer 1.

Sample Input 2:

4
9 9 9 9

Sample Output 2:

Hint 1

Hint 2

If the array were sorted, could you find the 4th largest element?

Approaches (2)

Approach 1

Approach 2

Sorting the array/list

We can find the 4th largest element by simply sorting the list, and returning the 4th element from the end.

Algorithm:

Sort the array in non-decreasing order
Return the fourth largest element
If the array has less than 4 elements, you can return the minimum integer value

Time Complexity

O(N * log(N)), Where N is the total number of elements in the array.

Since we are sorting the array

Space Complexity

O(1)

Since only constant space is required

(100% EXP penalty)

Fourth Largest Element in the Array

Console