algoadvance

Leetcode 414. Third Maximum Number

Problem Statement

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:

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

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

Input: nums = [2, 2, 3, 1]
Output: 1
Explanation: Note that the third distinct maximum here is 1 because the numbers 2 are considered repeats.

Clarifying Questions

  1. Q: Should I consider negative numbers as well?
    • A: Yes, the array can contain negative numbers.
  2. Q: What should I do if the array is empty?
    • A: The problem guarantees that the array will have at least one element, so this case does not need special handling.
  3. Q: Should I handle cases where input may contain duplicates?
    • A: Yes, you should only consider distinct numbers for the maximum values.

Strategy

  1. Use a set to store distinct values to easily eliminate duplicates.
  2. Iterate over the array and populate the set.
  3. If the set has less than three elements, return the maximum element.
  4. Otherwise, sort the set in descending order and retrieve the third element.

Code

import java.util.*;

public class ThirdMaximumNumber {
    public int thirdMax(int[] nums) {
        Set<Integer> distinctNumbers = new HashSet<>();
        for (int num : nums) {
            distinctNumbers.add(num);
        }

        // If there are less than 3 distinct numbers, return the maximum.
        if (distinctNumbers.size() < 3) {
            return Collections.max(distinctNumbers);
        }

        // Convert set to list and sort in descending order.
        List<Integer> sortedDistinctNumbers = new ArrayList<>(distinctNumbers);
        Collections.sort(sortedDistinctNumbers, Collections.reverseOrder());

        // Return the third maximum number.
        return sortedDistinctNumbers.get(2);
    }

    public static void main(String[] args) {
        ThirdMaximumNumber solution = new ThirdMaximumNumber();
        
        // Test Case 1
        int[] nums1 = {3, 2, 1};
        System.out.println(solution.thirdMax(nums1)); // Output: 1

        // Test Case 2
        int[] nums2 = {1, 2};
        System.out.println(solution.thirdMax(nums2)); // Output: 2
        
        // Test Case 3
        int[] nums3 = {2, 2, 3, 1};
        System.out.println(solution.thirdMax(nums3)); // Output: 1
    }
}

Time Complexity

  1. Adding to set: (O(n)) — Each insertion in a HashSet generally takes (O(1)) time, so inserting (n) elements takes (O(n)).
  2. Converting set to list and sorting: (O(n \log n)) — Sorting the list will take (O(n \log n)) time.
  3. Total Time Complexity: (O(n \log n))

This solution ensures that we find the third maximum number in an efficient manner by leveraging a set for uniqueness and sorting to easily retrieve the highest values.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI