Problem Explanation

The problem is asking to find the third maximum number in an array. We need to note that when it says the "third maximum number", it specifically refers to the third maximum "distinct" number.

Let's understand this using an example:

Suppose we have an array: [2, 2, 3, 1].

Here the maximum number is 3, the second maximum is 2 (not 2 again) and the third distinct maximum is 1.

However, an edge case can be when there are less than three distinct numbers in the array. In this case, we return the maximum number.

Let's consider an array: [1, 2].

Here, as the third maximum does not exist, we return the maximum, which is 2.

Solution Approach

Our approach to solve this problem would be to iterate over the array keeping track of the maximum, second maximum, and third maximum numbers till now for every current number. We need to process this in a way that for every number, if it's greater than the maximum till now, our current maximum updates to this new number. The old maximum becomes the second maximum, and the old second maximum becomes the third maximum.

This way, we make sure that at the end of the loop we have our third maximum number.

If the third maximum hasn't been updated from initial value (which means we didn't have three distinct numbers), we return the maximum number.

Let's see this in action:

Take an array: [3,4,5,2,4,5,2,6,7,4,9]

Here while iterating, these are our maximum, second maximum and third maximum values at each step:

Initial values: (-inf, -inf, -inf)

After 1st step: (3, -inf, -inf)

After 2nd step: (4, 3, -inf)

After 3rd step: (5, 4, 3)

After 4th step: (5, 4, 3)

After 5th step: (5, 4, 3)

After 6th step: (5, 4, 3)

After 7th step: (5, 4, 3)

After 8th step: (6, 5, 4)

After 9th step: (7, 6, 5)

After 10th step: (9, 7, 6)

As we can see, at the end we have our third maximum as 6.

Let's see how we can implement this approach in Python, Java, JavaScript, C++, and C#.

Python Solution

1
2python
3class Solution:
4    def thirdMax(self, nums: List[int]) -> int:
5        max1 = max2 = max3 = float('-inf')
6        for num in nums:
7            if num > max1:
8                max1, max2, max3 = num, max1, max2
9            elif max1 > num > max2:
10                max2, max3 = num, max2
11            elif max2 > num > max3:
12                max3 = num
13        return max1 if max3 == float('-inf') else max3

Java Solution

1
2java
3public class Solution {
4    public int thirdMax(int[] nums) {
5        Integer max1 = null;
6        Integer max2 = null;
7        Integer max3 = null;
8        for (Integer n : nums) {
9            if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
10            if (max1 == null || n > max1) {
11                max3 = max2;
12                max2 = max1;
13                max1 = n;
14            } else if (max2 == null || n > max2) {
15                max3 = max2;
16                max2 = n;
17            } else if (max3 == null || n > max3) {
18                max3 = n;
19            }
20        }
21        return max3 == null ? max1 : max3;
22    }
23}

JavaScript Solution

1
2javascript
3class Solution {
4    thirdMax(nums) {
5        let max1 = Number.NEGATIVE_INFINITY;
6        let max2 = Number.NEGATIVE_INFINITY;
7        let max3 = Number.NEGATIVE_INFINITY;
8        for (let num of nums) {
9            if (num > max1) {
10                [max1, max2, max3] = [num, max1, max2];
11            } else if (num < max1 && num > max2) {
12                [max2, max3] = [num, max2];
13            } else if (num < max2 && num > max3) {
14                max3 = num;
15            }
16        }
17        return max3 === Number.NEGATIVE_INFINITY ? max1 : max3;
18    }
19}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int thirdMax(vector<int>& nums) {
6        long max1 = LONG_MIN;
7        long max2 = LONG_MIN;
8        long max3 = LONG_MIN;
9        for (int num : nums) {
10            if (num > max1) {
11                max3 = max2;
12                max2 = max1;
13                max1 = num;
14            } else if (num < max1 && num > max2) {
15                max3 = max2;
16                max2 = num;
17            } else if (num < max2 && num > max3) {
18                max3 = num;
19            }
20        }
21        return max3 == LONG_MIN ? max1 : max3;
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int ThirdMax(int[] nums) {
5        long? max1 = null;
6        long? max2 = null;
7        long? max3 = null;
8        foreach (int n in nums) {
9            if (n.Equals(max1) || n.Equals(max2) || n.Equals(max3)) continue;
10            if (max1 == null || n > max1) {
11                max3 = max2;
12                max2 = max1;
13                max1 = n;
14            } else if (max2 == null || n > max2) {
15                max3 = max2;
16                max2 = n;
17            } else if (max3 == null || n > max3) {
18                max3 = n;
19            }
20        }
21        return max3 == null ? (int)max1 : (int)max3;
22    }
23}

Make sure to replace inf and null with the minimum possible numbers for the specific data type in your language of choice if it doesn't support inf and null. For instance, in C++, use LONG_MIN instead.# Time and Space Complexity

In all the above solutions, we only traverse the array once. Therefore, the time complexity is O(n), where n is the length of the given array.

As for the space complexity, we use a constant number of variables irrespective of the array size. Hence, the space complexity is O(1).

Testing the Solution

One of the best ways to verify our solution is by running multiple test cases including edge cases and looking at the output.

For instance, you can test the following scenarios:

• Array with less than three distinct integers: e.g [1,2]
• Array with three distinct integers: e.g [3,2,1]
• Array with more than three distinct integers. e.g [1,2,3,4,5]
• Array with duplicated integers, e.g [2,2,3,1]
• Empty array

Conclusion

Finding the third maximum number in an array is a common question in coding interviews. The key to the solution lies in tracking the three highest distinct numbers as we iterate through the array.

This problem teaches important aspects of algorithmic thinking, including understanding edge cases, processing and tracking data efficiently, and using appropriate data structures to solve a problem succinctly. It is often asked to assess how well a candidate can apply these principles in real-world practical coding problems.