700312. Third largest element
Third Largest Element
Slug: third-largest-element
Difficulty: Easy
Id: 700312
Topic Tags: Arrays, Data Structures
Company Tags: Amazon, Microsoft, MakeMyTrip
Summary
The problem asks to find the third largest element in an array. This is a basic array manipulation problem that requires iterating through the array and keeping track of the maximum and second maximum values.
Detailed Explanation
To solve this problem, we can iterate through the array from left to right, keeping track of the maximum value (first_max) and the second maximum value (second_max). We also keep track of the third maximum value (third_max) as we iterate. When we find an element that is greater than first_max, we update first_max and second_max. If the new element is equal to first_max but less than second_max, we update second_max with the new element. If the new element is less than both first_max and second_max, we update third_max with the new element.
Here's a step-by-step breakdown of the solution:
- Initialize three variables:
first_max,second_max, andthird_maxto negative infinity. - Iterate through the array:
- For each element, check if it is greater than
first_max. - If so, update
first_maxand setsecond_maxto the previous value offirst_max. Updatethird_maxwith the new element. - If the element is equal to
first_maxbut less thansecond_max, updatesecond_maxwith the new element. Leavethird_maxunchanged. - If the element is less than both
first_maxandsecond_max, updatethird_maxwith the new element.
- For each element, check if it is greater than
- Return the value of
third_max.
Time complexity: O(n), where n is the size of the array. We iterate through the array once, so the time complexity is linear.
Space complexity: O(1), since we only use a constant amount of space to store the three maximum values.
Optimized Solutions
Java
public int thirdLargest(int[] arr) {
int first_max = Integer.MIN_VALUE;
int second_max = Integer.MIN_VALUE;
int third_max = Integer.MIN_VALUE;
for (int num : arr) {
if (num > first_max) {
second_max = first_max;
first_max = num;
} else if (num == first_max && second_max < first_max) {
second_max = num;
} else if (num < first_max && num > second_max) {
third_max = second_max;
second_max = num;
}
}
return third_max != Integer.MIN_VALUE ? third_max : -1;
}