Sponsored
This approach involves first sorting the array and then selecting distinct maximums from the sorted array. We can use a set to easily manage distinct elements. After constructing a set, we check if the size of the set is at least 3; if so, we find the third largest by accessing the sorted array of distinct elements, otherwise, return the maximum element.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) as sorting is done in place with qsort.
1def thirdMax(nums):
2 distinct_nums = set(nums)
3 if len(distinct_nums) < 3:
4 return max(distinct_nums)
5 distinct_nums.remove(max(distinct_nums))
6 distinct_nums.remove(max(distinct_nums))
7 return max(distinct_nums)
8
9print(thirdMax([2, 2, 3, 1]))In the Python solution, we convert the list to a set for unique elements. We check for the size of the set; if it's less than three, we return the maximum. Otherwise, we remove the two largest distinct elements and return the next maximum which is the third distinct maximum.
This approach keeps track of the three largest distinct numbers iteratively as it processes the array. It uses variables to track them and updates them as it iterates through each number. This way, it can achieve O(n) time complexity without additional set or sorting overhead.
Time Complexity: O(n) because it performs a single pass over the array.
Space Complexity: O(1) as only constant space is used for tracking the maximums.
1
public class Solution {
public int ThirdMax(int[] nums) {
long first = long.MinValue, second = long.MinValue, third = long.MinValue;
foreach (int num in nums) {
if (num == first || num == second || num == third) continue;
if (num > first) {
third = second;
second = first;
first = num;
} else if (num > second) {
third = second;
second = num;
} else if (num > third) {
third = num;
}
}
return third == long.MinValue ? (int)first : (int)third;
}
public static void Main(string[] args) {
var solution = new Solution();
Console.WriteLine(solution.ThirdMax(new int[]{2, 2, 3, 1}));
}
}In C#, the solution mimics similar structural patterns with long types to prevent initial value conflicts, precisely capturing and returning distinct maximums based on their conditions met through the array processing. This single-loop structure keeps storage and operations efficient.