Third Maximum Number - Practice Coding Problems

Third Maximum Number - Problem

Array Sorting Easy

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.

Note: You must find the third distinct maximum, meaning duplicates are ignored when counting maximums.

Input & Output

Example 1 — Basic Case with Third Maximum

$ Input: nums = [3,2,1]

› Output: 1

💡 Note: Three distinct numbers exist: 3 (first max), 2 (second max), 1 (third max). Return 1.

Example 2 — Less than 3 Distinct Numbers

$ Input: nums = [1,2]

› Output: 2

💡 Note: Only 2 distinct numbers exist. Third maximum doesn't exist, so return the maximum: 2.

Example 3 — Array with Duplicates

$ Input: nums = [2,2,3,1]

› Output: 1

💡 Note: Distinct numbers: 3 (first max), 2 (second max), 1 (third max). Duplicates are ignored. Return 1.

Constraints

1 ≤ nums.length ≤ 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with possible duplicates: [3, 2, 1]

Find Distinct Maximums

Identify the 1st, 2nd, and 3rd largest distinct values

Return Result

Return 3rd maximum if exists, else return maximum

Key Takeaway

🎯 Key Insight: Only need to track the top 3 distinct values to determine the third maximum efficiently

Asked in

a Amazon 15 🍎 Apple 8 M Microsoft 6 G Google 4

The key insight is to track only the top 3 distinct maximum values. The optimal single-pass approach maintains three variables (first, second, third) and updates them as we scan through the array. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Find Third	O(n log n)	O(n)	Sort unique values in descending order and return the third element
Min Heap of Size 3	O(n log 3)	O(n)	Use a min heap of size 3 to efficiently track the three largest distinct elements
Single Pass Tracking	O(n)	O(1)	Track the three maximum distinct values in a single pass through the array

Sort and Find Third — Algorithm Steps

Step 1: Convert array to set to remove duplicates
Step 2: Sort unique values in descending order
Step 3: Return third element if exists, else return first (maximum)

Visualization

Tap to expand

Step-by-Step Walkthrough

Remove Duplicates

Convert to set to get unique values

Sort Descending

Sort unique values from largest to smallest

Pick Third

Return third element if exists, else return maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int solution(int* nums, int numsSize) {
    int unique[numsSize];
    int uniqueSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < uniqueSize; j++) {
            if (unique[j] == nums[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            unique[uniqueSize++] = nums[i];
        }
    }
    
    qsort(unique, uniqueSize, sizeof(int), compare);
    
    if (uniqueSize >= 3) {
        return unique[2];
    }
    return unique[0];
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Set and sorted list store unique elements

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Find Third — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler