Practice/Meta/Leetcode 414. Third Maximum Number

Leetcode 414. Third Maximum Number

CodingMust

Problem

Given an integer array and a positive integer k, find the kth largest distinct element in the array. Duplicate values should be treated as a single occurrence when determining distinct elements.

If there are fewer than k distinct elements in the array, return the maximum element instead.

Your goal is to implement an efficient solution that runs in O(n) time complexity with minimal additional space usage.

Requirements

1. Return the kth largest distinct value from the array
2. Treat duplicate values as a single distinct element
3. If fewer than k distinct values exist, return the maximum value
4. Achieve linear O(n) time complexity
5. Minimize space complexity (ideally O(1) for small k values)

Constraints

• 1 ≤ array length ≤ 104
• -231 ≤ array[i] ≤ 231 - 1
• 1 ≤ k ≤ 100
• The value of k is typically small (e.g., finding 3rd, 4th, or 5th largest)

Examples

Example 1:

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 Output: 3 Explanation: The distinct values sorted descending are [6, 5, 4, 3, 2, 1]. The 4th largest distinct value is 3.

Example 2:

Input: nums = [1, 2], k = 3 Output: 2 Explanation: There are only 2 distinct values. Since k > 2, return the maximum value which is 2.

Example 3:

Input: nums = [2, 2, 2, 2], k = 1 Output: 2 Explanation: All elements are the same, so there's only 1 distinct value. Return it.

Example 4:

Input: nums = [10, 9, 8, 7, 6, 5], k = 3 Output: 8 Explanation: All values are distinct. The 3rd largest is 8.