algoadvance

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example 1:

Input: nums = [3, 2, 1]
Output: 1
Explanation: The first distinct maximum is 3, the second distinct maximum is 2, and the third distinct maximum is 1.

Example 2:

Input: nums = [1, 2]
Output: 2
Explanation: The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2, 2, 3, 1]
Output: 1
Explanation: Note that the distinct numbers are [2, 3, 1], with the third maximum being 1.

Clarifying Questions

  1. Q: What range can the integers in nums take?
    A: The integers are within the range of standard 32-bit integer values (-2^31 to 2^31 - 1).

  2. Q: Can there be duplicate values in the array nums?
    A: Yes, there can be duplicate values.

  3. Q: What is the maximum possible length of the nums array?
    A: This will typically be constrained by the platform limits, but we can assume it fits within usual constraints for array processing problems (up to 10^5 elements is a reasonable assumption).

Strategy

  1. Distinct Values: Convert the list to a set to eliminate duplicate values.
  2. Sort and Check: Sort the distinct values in descending order and then check if there are at least three distinct values.
  3. Return the Result: If there are at least three distinct values, return the third one; otherwise, return the maximum value.

Time Complexity

Code

def thirdMax(nums):
    # Convert the list to a set to get distinct values
    distinct_nums = list(set(nums))
    
    # Sort the distinct values in descending order
    distinct_nums.sort(reverse=True)
    
    # Check the length and return the appropriate value
    if len(distinct_nums) >= 3:
        return distinct_nums[2]
    else:
        return distinct_nums[0]

# Example usage:
print(thirdMax([2, 2, 3, 1]))  # Output: 1
print(thirdMax([3, 2, 1]))     # Output: 1
print(thirdMax([1, 2]))        # Output: 2

This code first deduplicates the input list by converting it to a set, sorts it in descending order, and then checks the length to decide whether to return the third maximum or the first maximum as needed.

Try our interview co-pilot at AlgoAdvance.com