# Fourth Largest Element in the Array

Posted: 19 Jul, 2020

Difficulty: Easy

#### 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.
```

##### 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
```

Approach 1

Approach 2

For optimizing our initial approach and avoid sorting all the elements, we can maintain a min-heap of size 4, and at each index store the 4 largest elements that occurred before the current index. In the end, we would need to return the element at the top of the heap which is the 4th largest element.

Algorithm:

- We will use a min-heap to keep track of the largest 4 elements.
- Iterate through all elements of the array
- If the size of min-heap is smaller than 4, add the current element to it
- If the size is larger than 4, first compare the top element of the min-heap with the current element. If the current element is smaller, do nothing. Otherwise, remove the top element of the heap and insert the current element in it
- After iterating the array, the min-heap would contain the largest 4 elements of the array. Simply return the top element of the heap

SIMILAR PROBLEMS

# Two Sum II - Input Array Is Sorted

Posted: 4 Mar, 2022

Difficulty: Moderate

# Ninja And Matrix

Posted: 12 Apr, 2022

Difficulty: Easy

# Ninja In Interview

Posted: 13 Apr, 2022

Difficulty: Easy

# Missing Number

Posted: 17 Apr, 2022

Difficulty: Easy

# Min Heap

Posted: 5 May, 2022

Difficulty: Moderate