Third Maximum Number in Java
Finding the third largest unique integer in an array is the aim of the Java challenge known as the Third Maximum Number Problem. To do this, find the third highest value while making sure it is not the same as the first two highest values.
Example 1:
Input:
nums = {23,45,67,432,90}
Output:
67
Explanation:
While traversing through the array we maintain record of three largest distinct numbers. Here the 1st Largest number is 432, 2nd Largest number is 90 and 3rd Largest number is 67. So the output is 67
Example 2:
Input:
nums = {10, 20, 30, 40, 50};
Output:
Third largest number: 20
Explanation:
While traversing through the array we maintain record of three largest distinct numbers. Here the 1st Largest number is 50, 2nd Largest number is 40 and 3rd Largest number is 30. So, the output is 20
Approach 1: Sorting
Algorithm
Step 1: The array should be sorted in decreasing order.
Step 2: Go through the sorted array until you come upon the third unique element.
Step 3: Provide the third component back.
FileName: ThirdLargestNumber.java
import java.util.Arrays;
public class ThirdLargestNumber {
public static int thirdMax(int[] nums) {
Arrays.sort(nums);
int count = 1;
int n = nums.length;
for (int i = n - 2; i >= 0; i--) {
if (nums[i] != nums[i + 1]) {
count++;
}
if (count == 3) {
return nums[i];
}
}
return nums[n - 1];
}
public static void main(String[] args) {
int[] nums = {23, 45, 67, 432, 90};
System.out.println("Third largest number: " + thirdMax(nums));
}
}
Output:
Third largest number: 67
Complexity Analysis:
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as no additional space is used.
Approach 2: Using TreeSet
Algorithm:
Step 1: Using TreeSet for unique collection of Integers.
Step 2: Insert each element into the TreeSet as iterating through the array.
Step 3: Retrieve the least element in the TreeSet if Size is more than 3.
Step 4: Output the TreeSet initial element which is the third-biggest distinct integer.
FileName: ThirdLargestNumber.java
import java.util.*;
public class ThirdLargestNumber {
public static int thirdMax(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for (int num : nums) {
set.add(num);
if (set.size() > 3) {
set.remove(set.first());
}
}
if (set.size() < 3) {
return set.last();
} else {
return set.first();
}
}
public static void main(String[] args) {
int[] nums = {23, 45, 67, 432, 90};
System.out.println("Third largest number: " + thirdMax(nums));
}
Output:
Third largest number: 67
Complexity Analysis:
Time Complexity: O(n log k), because of TreeSet operations, where k is 3.
Space Complexity: O(k) for the TreeSet.
Approach 3: Using Variables
Algorithm:
Step 1: Set up three variables with the first, second, and third greatest integers as their initial values.
Step 2: Iterate over the array, changing these variables as necessary.
Step 3: Verify that the first two largest integers and the third greatest number are not the same.
Step 4: Give back the third biggest integer.
FileName: ThirdLargestNumber.java
import java.util.*;
public class ThirdLargestNumber {
public static int thirdMax(int[] nums) {
Integer first = null, second = null, third = null;
for (Integer num : nums) {
if (num.equals(first) || num.equals(second) || num.equals(third)) {
continue;
}
if (first == null || num > first) {
third = second;
second = first;
first = num;
} else if (second == null || num > second) {
third = second;
second = num;
} else if (third == null || num > third) {
third = num;
}
}
return third != null ? third : first;
}
public static void main(String[] args) {
int[] nums = {23, 45, 67, 432, 90};
System.out.println("Third largest number: " + thirdMax(nums));
}
}
Output:
Third largest number: 67
Complexity Analysis:
Time Complexity: O(n) as we traverse the array only once.
Space Complexity: O(1) as no additional space is used.