[Array] Third Maximum Number - Easy

To find the third maximum number in an array, we need to get the third largest unique number from a list of integers. If we do not have three different numbers, we should return the maximum number. We can do this in different ways. We can sort the array or use data structures like sets to get unique values.

In this article, we will look at different ways to find the third maximum number in an array. We will give examples in Java, Python, and C++. We will first talk about the problem. Then, we will show two main methods. One method uses sorting and the other uses sets. Finally, we will show a better solution that uses three variables to be more efficient. Here is what we will talk about:

• [Array] Finding the Third Maximum Number in an Array - Easy
• Understanding the Problem Statement for Third Maximum Number
• Approach 1 Using Sorting Method in Java
• Approach 1 Using Sorting Method in Python
• Approach 1 Using Sorting Method in C++
• Approach 2 Using Set to Find Third Maximum in Java
• Approach 2 Using Set to Find Third Maximum in Python
• Approach 2 Using Set to Find Third Maximum in C++
• Optimized Approach Using Three Variables in Java
• Optimized Approach Using Three Variables in Python
• Optimized Approach Using Three Variables in C++
• Frequently Asked Questions

If you want to read more about similar topics, you can check these articles: Array Two Sum - Easy, Array Best Time to Buy and Sell Stock - Easy, and Array Contains Duplicate - Easy.

Understanding the Problem Statement for Third Maximum Number

We face the problem of finding the third maximum number in an array. This means we need to find the third largest number that is different from the others in a list of numbers. If the array has less than three different numbers, we should just give back the largest number.

Problem Definition

• Input: An array of integers.
• Output: The third maximum number or the maximum number if there are not three distinct integers.

Example Scenarios

1. Example 1:
   • Input: [3, 2, 1]
   • Output: 1 (this is the third maximum)
2. Example 2:
   • Input: [1, 2]
   • Output: 2 (this is the maximum since we do not have three distinct numbers)
3. Example 3:
   • Input: [2, 2, 3, 1]
   • Output: 1 (this is the third maximum)

Constraints

• The integers can be both negative or positive.
• The input array can have duplicates. We will ignore these when we count the distinct numbers.

In this article, we will look at different ways to find the third maximum number in an array. We will use programming languages like Java, Python, and C++.

Approach 1 Using Sorting Method in Java

In Java, we can find the third maximum number in an array by using sorting. We sort the array in descending order. Then, we can easily get the third distinct maximum number.

Implementation Steps:

1. Change the array into a set to remove duplicates.
2. Change the set back to an array or list.
3. Sort the array in descending order.
4. Return the third element if it is there. If not, return the maximum element.

Java Code Example:

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class ThirdMaximumNumber {
    public static int thirdMax(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        // Change set to an array
        Integer[] uniqueNums = set.toArray(new Integer[0]);
        
        // Check the length of unique numbers
        if (uniqueNums.length < 3) {
            return uniqueNums[uniqueNums.length - 1]; // Return max if less than 3 unique numbers
        }
        
        // Sort in descending order
        Arrays.sort(uniqueNums, (a, b) -> b - a);
        
        return uniqueNums[2]; // Return the third maximum
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1};
        System.out.println(thirdMax(nums)); // Output: 1
    }
}

Explanation:

• We use TreeSet to help with the uniqueness of the elements.
• The final sort is in descending order. This way, we can easily get the third maximum.
• This method takes time O(n log n) because of sorting. This is good for normal cases.

This way gives us a simple solution to find the third maximum number in an array by sorting in Java. For other similar problems, we can check articles like Array: Two Sum and Array: Maximum Subarray.

Approach 1 Using Sorting Method in Python

To find the third maximum number in an array using the sorting method in Python, we can do a few simple steps.

1. Remove Duplicates: We change the array to a set. This way, we get rid of duplicates.
2. Sort the Array: We sort the numbers from biggest to smallest.
3. Return the Third Element: We check if the third element exists. If it does, we return it. If not, we return the biggest number.

Here is a simple way to use this method:

def third_max(nums):
    # Remove duplicates by converting to a set
    unique_nums = list(set(nums))
    
    # Sort the unique numbers in descending order
    unique_nums.sort(reverse=True)
    
    # Return the third maximum or the maximum if not enough elements
    return unique_nums[2] if len(unique_nums) >= 3 else unique_nums[0]

# Example usage
nums = [3, 2, 1]
print(third_max(nums))  # Output: 1

nums = [1, 2]
print(third_max(nums))  # Output: 2

nums = [2, 2, 3, 1]
print(third_max(nums))  # Output: 1

Explanation of the Code:

• We use set() to remove duplicates from the list.
• Then we use sort() to order the list from biggest to smallest.
• At last, we check if we have at least three unique numbers. If we do, we take the third one. If not, we take the biggest number.

This sorting method is easy and works well to find the third maximum number in an array. For more details on how to work with arrays, you can look at Array Contains Duplicate.

Approach 1 Using Sorting Method in C++

To find the third maximum number in an array using the sorting method in C++, we can follow these steps:

1. Sort the Array: First, we sort the array in descending order.
2. Remove Duplicates: We go through the sorted array and collect unique values.
3. Return Third Maximum: We check if there are at least three unique numbers. If yes, we return the third one.

C++ Code Example:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

int thirdMax(std::vector<int>& nums) {
    std::set<int> unique_nums(nums.begin(), nums.end());
    
    if (unique_nums.size() < 3) {
        return *unique_nums.rbegin(); // Return the maximum if less than 3 unique numbers
    }
    
    std::vector<int> sorted_unique_nums(unique_nums.begin(), unique_nums.end());
    std::sort(sorted_unique_nums.rbegin(), sorted_unique_nums.rend()); // Sort in descending order
    return sorted_unique_nums[2]; // Return the third maximum
}

int main() {
    std::vector<int> nums = {3, 2, 1};
    std::cout << "Third Maximum Number: " << thirdMax(nums) << std::endl; // Output: 1
    return 0;
}

Explanation of the Code:

• The code use a set to handle duplicates and keep only unique elements.
• After that, we convert the set back to a vector and sort the vector in descending order.
• Finally, we check if we have at least three unique numbers and return the third maximum.

This method has a time complexity of O(n log n) because of the sorting step. It is a simple way to find the third maximum number in an array using C++.

Approach 2 Using Set to Find Third Maximum in Java

In Java, we can use a Set to easily find the third maximum number in an array. A Set takes care of duplicate values. This lets us look at only unique numbers. Let’s see how we do this:

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class ThirdMaximum {
    public static int thirdMax(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        
        for (int num : nums) {
            set.add(num);
            if (set.size() > 3) {
                set.remove(set.first()); // Remove the smallest number
            }
        }

        // If we have less than 3 unique numbers, return the maximum
        if (set.size() < 3) {
            return set.last();
        }
        
        return set.first(); // This is the third maximum
    }

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

Explanation:

• TreeSet: We use a TreeSet to keep unique numbers in order.
• Adding Elements: As we go through the array, we add each number to the set.
• Maintaining Size: If the set has more than 3 numbers, we remove the smallest one.
• Result Calculation: In the end, if we have less than 3 numbers, we return the maximum. If we have enough, the smallest number in the set is the third maximum.

This way is simple and works well. It uses the features of a set to keep numbers unique and in order. For more array programming challenges, visit Best Online Tutorial.

Approach 2 Using Set to Find Third Maximum in Python

To find the third maximum number in an array using a set in Python, we can use the special features of sets. Sets help us by removing duplicate values. The steps are simple. We will change the list to a set, sort it, and then get the third maximum.

Steps:

1. Change the array to a set to remove duplicates.
2. Sort the set from high to low.
3. Check if the set has at least three numbers. If not, we will return the highest number.
4. Get the third number from the sorted set.

Python Code:

def thirdMax(nums):
    unique_nums = set(nums)
    sorted_nums = sorted(unique_nums, reverse=True)
    
    if len(sorted_nums) < 3:
        return sorted_nums[0]
    
    return sorted_nums[2]

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

nums = [1, 2]
print(thirdMax(nums))  # Output: 2

nums = [2, 2, 3, 1]
print(thirdMax(nums))  # Output: 1

This method finds the third maximum number in an easy way. It uses the set for unique values and sorts them. If you want to learn more about arrays, you can check Array Contains Duplicate or Array Remove Duplicates from Sorted Array.

Approach 2 Using Set to Find Third Maximum in C++

In C++, we can use a std::set to find the third maximum number in an array. A set helps us by removing duplicates and keeping the numbers sorted. This makes it a good choice for our task.

Steps:

1. We insert each number from the array into the set.
2. After we add all numbers, we check how many unique numbers we have.
3. If there are less than 3 unique numbers, we return the maximum number. If not, we find the third maximum.

C++ Code Example:

#include <iostream>
#include <set>
#include <vector>

int thirdMax(std::vector<int>& nums) {
    std::set<int> unique_nums;

    for (int num : nums) {
        unique_nums.insert(num);
    }

    if (unique_nums.size() < 3) {
        return *unique_nums.rbegin(); // Return the maximum
    }

    auto it = unique_nums.end();
    std::advance(it, -3); // Move iterator to the third last element
    return *it; // Return the third maximum
}

int main() {
    std::vector<int> nums = {3, 2, 1};
    std::cout << "Third Maximum: " << thirdMax(nums) << std::endl; // Output: 1

    nums = {1, 2};
    std::cout << "Third Maximum: " << thirdMax(nums) << std::endl; // Output: 2

    nums = {2, 2, 3, 1};
    std::cout << "Third Maximum: " << thirdMax(nums) << std::endl; // Output: 1

    return 0;
}

Explanation:

• We use std::set<int> unique_nums to keep unique numbers from the array.
• The check if (unique_nums.size() < 3) helps us when there are not three different numbers.
• We use std::advance(it, -3) to move the iterator to the third maximum number.

This method finds the third maximum number quickly. It has O(n log n) complexity because of the log cost when we add numbers into the set.

Optimized Approach Using Three Variables in Java

To find the third maximum number in an array using a simple way in Java, we can use three variables. These variables help us keep track of the first, second, and third maximum numbers. This method works in O(n) time and does not need extra space for sorting or keeping elements in a set.

Here is how we can do this:

public class ThirdMaximum {
    public static int thirdMax(int[] nums) {
        Long first = null, second = null, third = null;
        
        for (int num : nums) {
            if (num == first || num == second || num == third) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = (long) num;
            } else if (second == null || num > second) {
                third = second;
                second = (long) num;
            } else if (third == null || num > third) {
                third = (long) num;
            }
        }
        
        return third == null ? first.intValue() : third.intValue();
    }

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

Explanation:

• Variables: We start with first, second, and third as null. They will hold the three highest different numbers.
• Loop: We go through each number in the array.
• Conditions:
  • We skip repeated numbers.
  • We update first, second, and third depending on the current number.
• Return: If third is still null, it means we do not have enough different numbers. So, we return first.

This method quickly finds the third maximum number in an easy way. It is clear and works well. For more articles about arrays, check Array Best Time to Buy and Sell Stock - Easy.

Optimized Approach Using Three Variables in Python

To find the third maximum number in an array with a better way using three variables in Python, we can keep track of the first, second, and third maximum values while we go through the array. This way is good because it only takes O(n) time and O(1) space.

Here is how we can do it:

def thirdMax(nums):
    first = second = third = float('-inf')
    
    for num in nums:
        if num in (first, second, third):
            continue
        if num > first:
            first, second, third = num, first, second
        elif num > second:
            second, third = num, second
        elif num > third:
            third = num

    return third if third != float('-inf') else first

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

nums = [1, 2]
print(thirdMax(nums))  # Output: 2

nums = [2, 2, 3, 1]
print(thirdMax(nums))  # Output: 1

Explanation of the Code

• We start with three variables (first, second, and third) set to negative infinity. This helps to include all values in the array.
• While we go through each number in the array, we:
  • Skip duplicate values so we can find unique maximums.
  • Update our three variables based on the current number to keep the largest three unique values.
• In the end, we check if third was updated. If it was not updated, we return first because it would be the maximum number if there are not three different numbers.

This way helps us find the third maximum number in just one go through the array. This is good for larger datasets. For more practice with arrays, you can read this article on Array Best Time to Buy and Sell Stock.

Optimized Approach Using Three Variables in C++

In this approach, we find the third maximum number in an array. We use three variables to keep track of the first, second, and third maximum values. This method works in O(n) time and O(1) space. It is good for big datasets.

Implementation in C++

#include <iostream>
#include <vector>
#include <limits>

int thirdMax(std::vector<int>& nums) {
    long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
    
    for (int num : nums) {
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second && num < first) {
            third = second;
            second = num;
        } else if (num > third && num < second) {
            third = num;
        }
    }
    
    return (third == LONG_MIN) ? first : third;
}

int main() {
    std::vector<int> nums = {3, 2, 1};
    std::cout << "Third Maximum Number: " << thirdMax(nums) << std::endl; // Output: 1
    
    std::vector<int> nums2 = {1, 2};
    std::cout << "Third Maximum Number: " << thirdMax(nums2) << std::endl; // Output: 2
    
    std::vector<int> nums3 = {2, 2, 3, 1};
    std::cout << "Third Maximum Number: " << thirdMax(nums3) << std::endl; // Output: 1

    return 0;
}

Explanation

• Variables: We start first, second, and third with the smallest possible value. This is LONG_MIN.
• Loop: We go through each number in the array. We update the maximum values when needed.
• Return Value: If third is still LONG_MIN, it means there are not three different numbers. So we return first. If not, we return third.

This method works well with duplicates. It only counts different numbers for the third maximum.

For more about array problems, you can check Array Maximum Subarray - Easy.

Frequently Asked Questions

1. What is the third maximum number in an array?

The third maximum number in an array is the third largest unique number. If the array has less than three unique numbers, we usually return the maximum number. It is important to know how to find the third maximum number fast for many programming tasks. This article gives different ways to solve this problem.

2. How can I find the third maximum number using sorting in Java?

To find the third maximum number in Java using sorting, we can first sort the array in descending order. After that, we can check the unique elements. Here is a simple code:

import java.util.Arrays;

public class ThirdMaximum {
    public static int thirdMax(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length - 3]; // Make sure to handle unique values
    }
}

This way is easy but may not be the fastest. We can look at other methods in this article.

3. Is using a set the best way to find the third maximum number in Python?

Using a set in Python is a good way to find the third maximum number. It helps remove duplicates automatically. We can change the list to a set, then sort the elements and get the third maximum value easily. Here is a short code example:

def third_max(nums):
    unique_nums = list(set(nums))
    unique_nums.sort(reverse=True)
    return unique_nums[2] if len(unique_nums) >= 3 else max(unique_nums)

This way makes sure we only look at unique values to find the third maximum.

4. Can I find the third maximum number without sorting the array in C++?

Yes, we can find the third maximum number in C++ without sorting. We can use three variables to keep track of the first, second, and third maximums. This way is faster because it runs in O(n) time. Here is a code example:

#include <iostream>
#include <limits.h>

int thirdMax(std::vector<int>& nums) {
    long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
    for (int num : nums) {
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second && num < first) {
            third = second;
            second = num;
        } else if (num > third && num < second) {
            third = num;
        }
    }
    return third == LONG_MIN ? first : third;
}

This better way is good for big datasets and helps us find the third maximum number quickly.

5. What should I do if my array has fewer than three unique numbers?

If our array has less than three unique numbers, we usually return the maximum number. This is important when we find the third maximum number in an array. The ways in this article will help us implement this logic well in different programming languages. For more problems like this, we can check articles like Array Contains Duplicate or Array Maximum Subarray for more help.