Problem

Given an array of distinct elements, find the largest three elements. The solution should have a time complexity of O(n) and use O(1) extra space.

Examples

Example 1:

1
2
3

Input: [10, 4, 3, 50, 23, 90]
Output: [90, 50, 23]
Explanation: The three largest elements are 90, 50, and 23.

Example 2:

1
2
3

Input: [12, 13, 1, 10, 34, 1]
Output: [34, 13, 12]
Explanation: The three largest elements are 34, 13, and 12.

Solution

Method 1 - Iteration

To find the largest three elements in a single pass over the array, we can maintain three variables to store the three largest elements found so far. As we iterate through the array:

  1. If the current element is larger than the largest of the three, update the three variables accordingly.
  2. If the current element is larger than the second largest but not the largest, update the second and third largest elements.
  3. If the current element is larger than the third largest but not the other two, update the third largest element.

Approach

  1. Initialize three variables first, second, and third to store the largest, second largest, and third largest elements respectively. Set them to very low values initially.
  2. Traverse the array once, updating the variables based on the current element’s value compared to the three largest elements found so far.
  3. After traversal, the three variables will contain the largest three elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public int[] findLargestThree(int[] arr) {
        if (arr.length < 3) throw new IllegalArgumentException("Array must have at least three elements.");
        
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE, third = Integer.MIN_VALUE;
        
        for (int num : arr) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second) {
                third = second;
                second = num;
            } else if (num > third) {
                third = num;
            }
        }
        
        return new int[]{first, second, third};
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr1 = {10, 4, 3, 50, 23, 90};
        int[] arr2 = {12, 13, 1, 10, 34, 1};
        
        System.out.println(Arrays.toString(solution.findLargestThree(arr1))); // Output: [90, 50, 23]
        System.out.println(Arrays.toString(solution.findLargestThree(arr2))); // Output: [34, 13, 12]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def findLargestThree(self, arr: List[int]) -> List[int]:
        if len(arr) < 3:
            raise ValueError("Array must have at least three elements.")
        
        first: int = float('-inf')
        second: int = float('-inf')
        third: int = float('-inf')
        
        for num in arr:
            if num > first:
                third = second
                second = first
                first = num
            elif num > second:
                third = second
                second = num
            elif num > third:
                third = num
        
        return [first, second, third]

# Example usage:
solution = Solution()
print(solution.findLargestThree([10, 4, 3, 50, 23, 90])) # Output: [90, 50, 23]
print(solution.findLargestThree([12, 13, 1, 10, 34, 1])) # Output: [34, 13, 12]

Complexity

  • ⏰ Time complexity: O(n) because we only make a single pass through the array.
  • 🧺 Space complexity: O(1) since we are using a fixed number of additional variables.