Find Three Largest Numbers

Tags

Find Three Largest Numbers

Category

Searching

Difficulty

Easy

Problem Statement

Given an array of at least three integers, find and return the three largest numbers in sorted ascending order. The returned array should have exactly three elements. Duplicates are allowed — if the largest number appears three times, the result may contain it three times.

Intuition

Maintain a sorted triplet of the three largest values seen so far. As we scan through the array, each element is compared against the current third-largest, then the second-largest, then the largest, and inserted into the correct position if it qualifies. This avoids sorting the entire array.

Approach

  1. Initialize a result array of three elements, all set to negative infinity.
  2. Iterate through each number in the array.
  3. For each number, compare against the three tracked values from largest to smallest:
    • If it is larger than the current largest, shift the other two down and place it as the new largest.
    • Else if it is larger than the second largest, shift the third down and place it as the new second largest.
    • Else if it is larger than the third largest, place it as the new third largest.
  4. Return the result array.

Pseudocode

function findThreeLargestNumbers(array):
    threeLargest = [-infinity, -infinity, -infinity]
    for num in array:
        updateLargest(threeLargest, num)
    return threeLargest

function updateLargest(threeLargest, num):
    if num > threeLargest[2]:
        shiftAndUpdate(threeLargest, num, 2)
    else if num > threeLargest[1]:
        shiftAndUpdate(threeLargest, num, 1)
    else if num > threeLargest[0]:
        shiftAndUpdate(threeLargest, num, 0)

function shiftAndUpdate(array, num, idx):
    for i from 0 to idx - 1:
        array[i] = array[i + 1]
    array[idx] = num

Time & Space Complexity

  • Time: O(n) — Single pass through the array with constant-time comparisons per element.
  • Space: O(1) — Only a fixed-size array of three elements is maintained.

Key Insights

  • This generalizes to finding the k largest numbers in O(n) time with O(k) space.
  • No sorting is needed, making this more efficient than sorting when k is much smaller than n.
  • The shift-and-update pattern maintains the three values in sorted order.
  • This problem requires not just the maximum but the top three, so a simple max-tracking variable is insufficient.

Edge Cases

  • Exactly three elements — return them sorted.
  • Array contains duplicate values — duplicates can appear in the result.
  • All elements are the same — return three copies of that value.
  • Array contains negative numbers — the logic works with negative infinity initialization.
  • Very large array — still O(n) with minimal overhead.

Linked mentions