876296. Largest three distinct elements
Easy
Largest three distinct elements
Slug: largest-three-distinct-elements
Difficulty: Easy
Id: 876296
Topic Tags: Sorting, Greedy, Arrays
Company Tags: None
Summary
Given an array of integers, find the three largest distinct elements in it. This problem is a classic example of a greedy algorithm and requires a basic understanding of sorting and arrays.
Detailed Explanation
To solve this problem, we can use a simple sorting approach followed by a loop to find the three largest distinct elements. Here's a step-by-step breakdown:
- First, sort the array in descending order (largest to smallest).
- Initialize three variables
max1,max2, andmax3to store the three largest distinct elements. - Iterate through the sorted array from left to right.
- For each element, check if it is not equal to any of the previously found maximum values (
max1,max2, ormax3). If it's not equal, update the corresponding maximum value (e.g., if the current element is larger thanmax1, updatemax1). - Continue iterating until all elements have been processed.
- The three largest distinct elements are stored in
max1,max2, andmax3.
Time complexity: O(n log n) due to sorting Space complexity: O(1) as we only need a few extra variables
Optimized Solutions
Java
import java.util.Arrays;
public class LargestThreeDistinctElements {
public static int[] largestThree(int[] arr) {
Arrays.sort(arr);
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
for (int num : arr) {
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2 && num != max1) {
max3 = max2;
max2 = num;
} else if (num > max3 && num != max1 && num != max2) {
max3 = num;
}
}
return new int[] {max1, max2, max3};
}
}