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.
1using System;
2using System.Linq;
3
4public class Solution {
5 public int ThirdMax(int[] nums) {
6 var distinctNums = nums.Distinct().OrderByDescending(x => x).ToList();
7 return distinctNums.Count < 3 ? distinctNums.Max() : distinctNums[2];
8 }
9 public static void Main(string[] args) {
10 var solution = new Solution();
11 int[] nums = {2, 2, 3, 1};
12 Console.WriteLine(solution.ThirdMax(nums));
13 }
14}The C# solution uses LINQ to achieve distinct set elements. The list is ordered in descending order, and if its count is less than three, the maximum is returned. Otherwise, the third element in the list (third maximum) is returned.
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
The Java solution also uses long to differentiate uninitialized state for three distinct maximums and completes insightfully by returning the correct maximum based on the presence of a true third maximum distinct value. First three checks assign new maximum values when their conditions are satisfied.