Find the Third Largest Element in an Array

Title: Find the Third Largest Element in an Array

In this guide, you’ll learn how to find the third largest element in an array using a single pass through the data. We’ll frame the problem, build a clean linear-time solution in Java with three cascading trackers, trace it by hand on a fresh input, and then stress test it against the edge cases that make this problem subtler than its two-tracker cousin.

The jump from “second largest” to “third largest” looks small, but it introduces a cascading demotion step that trips up candidates. By the end of this article you’ll have a program you can defend under follow-up questions and a mental model for extending the pattern to the K-th largest problem.

Understanding the Problem

Given an integer array, we want to return the third largest distinct value. For {10, 10, 7, 5, 7, 3} the three distinct top values are 10, 7, and 5, so the third largest is 5. Duplicates of a higher tier do not count toward lower tiers. If the array has fewer than three distinct values, no third largest exists and the program should raise an error rather than silently return a misleading value.

The core insight is that we only need to remember three numbers at any time: the current largest, secondLargest, and thirdLargest. When we see a new maximum, we must cascade the previous values down one tier each so that no information is lost.

Approach to Find the Third Largest Element

We can solve this in one linear pass by maintaining three running values and cascading them on each new maximum. The algorithm steps are:

1. Validate that the array is non-null and has at least three elements; otherwise throw an exception.
2. Initialize largest, secondLargest, and thirdLargest to Integer.MIN_VALUE.
3. Iterate over every element in the array.
4. If the current element is strictly greater than largest, cascade: push secondLargest into thirdLargest, push largest into secondLargest, and set largest to the current element.
5. Otherwise, if the current element is strictly less than largest and strictly greater than secondLargest, push secondLargest into thirdLargest and set secondLargest to the current element.
6. Otherwise, if the current element is strictly less than secondLargest and strictly greater than thirdLargest, update thirdLargest only.
7. After the loop, if thirdLargest is still Integer.MIN_VALUE, no distinct third largest exists; throw an exception.
8. Return thirdLargest.

Java Program

Here is the complete, compilable program that implements the approach above.

public class ThirdLargestElement {
    public static int findThirdLargest(int[] numbers) {
        if (numbers == null || numbers.length < 3) {
            throw new IllegalArgumentException("Array must contain at least three elements");
        }
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        int thirdLargest = Integer.MIN_VALUE;
        for (int i = 0; i < numbers.length; i++) {
            int current = numbers[i];
            if (current > largest) {
                thirdLargest = secondLargest;
                secondLargest = largest;
                largest = current;
            } else if (current < largest && current > secondLargest) {
                thirdLargest = secondLargest;
                secondLargest = current;
            } else if (current < secondLargest && current > thirdLargest) {
                thirdLargest = current;
            }
        }
        if (thirdLargest == Integer.MIN_VALUE) {
            throw new IllegalArgumentException("No distinct third largest element exists");
        }
        return thirdLargest;
    }

    public static void main(String[] args) {
        int[] numbers = {12, 35, 1, 10, 34, 1};
        int thirdLargest = findThirdLargest(numbers);
        System.out.println("The third largest element is: " + thirdLargest);
    }
}

Explanation of the Program

The guard clause at the top of findThirdLargest rejects a null array or one with fewer than three elements, because the problem is undefined for those inputs. Failing fast with IllegalArgumentException is better than returning a sentinel that a caller might silently propagate.

We seed all three trackers with Integer.MIN_VALUE so that any real integer in the array will beat the initial values. Caching the current element into a local variable current keeps the three-way comparison readable and avoids repeated array indexing inside the hot branches.

The first branch handles a new maximum and performs the full cascade: the previous secondLargest drops into thirdLargest, the previous largest drops into secondLargest, and largest takes the new value. The order of these three assignments matters; swapping them would overwrite the values we still need to move down.

The second branch catches a new second-tier value. The condition current < largest && current > secondLargest is the key invariant: the strict < largest rejects duplicates of the top tier, and the strict > secondLargest rejects duplicates of the second tier as well as any value already below it. The third branch repeats this pattern one tier down.

The final guard catches arrays that have at most two distinct values, like {7, 7, 5}. Rather than returning Integer.MIN_VALUE, which the caller might mistake for a real answer, we surface the issue at the call site.

Step-by-Step Trace

Let’s run the algorithm on the input {15, 8, 15, 12, 10, 20}, which should finish with largest = 20, secondLargest = 15, and thirdLargest = 12. Each row below shows the state after that iteration completes.

Invariant: at the end of each iteration, largest, secondLargest, and thirdLargest hold the top three distinct values seen so far, in order, with Integer.MIN_VALUE as a placeholder when fewer than three distinct values have been encountered. Iteration 6 is the pedagogical payoff: a new maximum triggers both demotions in one step, which is why the three assignments inside the first branch must execute in the written order.

Examples

The following examples show the program behaving on three different shapes of input.

Example 1: Mixed Positive Integers

int[] numbers = {12, 35, 1, 10, 34, 1};
int thirdLargest = findThirdLargest(numbers);
System.out.println(thirdLargest);
// Output: 12

The distinct values sorted in descending order are 35, 34, 12, 10, 1, so the third largest is 12. The repeated 1 is harmless because it never beats any of the three trackers.

Example 2: Array of Negative Numbers

int[] numbers = {-5, -2, -10, -1, -8};
int thirdLargest = findThirdLargest(numbers);
System.out.println(thirdLargest);
// Output: -5

An all-negative array is where seeding with 0 would quietly fail: the trackers would never update because every element is less than zero. Seeding with Integer.MIN_VALUE keeps the algorithm correct, and the distinct top three are -1, -2, -5, so the third largest is -5.

Example 3: Multiple Duplicates of Higher Tiers

int[] numbers = {25, 25, 10, 25, 15, 20};
int thirdLargest = findThirdLargest(numbers);
System.out.println(thirdLargest);
// Output: 15

The maximum 25 appears three times, but the duplicates fall through all three branches and never pollute the lower tiers. The distinct top three are 25, 20, 15, so the third largest is 15.

Common Mistakes to Avoid

These are the specific pitfalls candidates run into while coding this problem under pressure.

• Three independent if branches – updating largest, secondLargest, and thirdLargest with three parallel if statements loses the demotion step; a new maximum ends up stored in all three trackers at once. Use the cascading else if structure so each element enters exactly one branch.
• Assigning in the wrong order inside the cascade – writing largest = current; secondLargest = largest; thirdLargest = secondLargest; overwrites largest before you can read its old value. Assign bottom up: thirdLargest first, then secondLargest, then largest.
• Initializing to zero – fails on arrays containing only negative numbers because 0 is wrongly reported as a candidate top-tier value. Initialize all three trackers to Integer.MIN_VALUE.
• Using non-strict comparisons – replacing current > secondLargest with current >= secondLargest lets a duplicate of the second tier demote the second tier into the third tier, silently corrupting the answer. Keep every comparison strict.
• Silently returning Integer.MIN_VALUE when fewer than three distinct values exist – the caller cannot distinguish a genuine answer from the sentinel. Throw IllegalArgumentException so the problem surfaces at the call site.

Edge Cases to Test

Walk through these boundary inputs before claiming the solution is complete. The order below mirrors how often each case shows up in interview grading rubrics.

• Empty array
• Array with fewer than three elements
• Array with exactly three distinct values
• Array with only two distinct values
• All identical elements
• All negative elements
• Strictly ascending input
• Strictly descending input
• Multiple duplicates of the largest and second largest
• Integer.MIN_VALUE present in the array
• Null array reference

Additional Considerations

The algorithm runs in O(n) time because it performs a single pass over the array and does at most three comparisons and three assignments per element. Space usage is O(1): only three integer trackers plus the loop index and the cached current value, independent of input size.

A sort-based solution works too but costs O(n log n) time and either O(1) or O(n) space depending on the sort, and the “third distinct” requirement needs a second pass over the sorted array to skip duplicates. A min-heap of size three is also possible but adds log-factor overhead for no real benefit at this scale.

One edge case worth calling out explicitly: an array that already contains Integer.MIN_VALUE. Our final guard checks thirdLargest == Integer.MIN_VALUE to detect the fewer-than-three-distinct-values case, which collides with a legitimate Integer.MIN_VALUE input value. In a production setting you would use three boolean flags or three OptionalInt return slots to disambiguate; for interview purposes it is enough to mention the collision aloud.

Interview Follow-up Questions

Interviewers almost always probe deeper after the base solution works. Expect variants along these lines.

• What if duplicates of the top tiers should count? – loosen each comparison to >= and drop the distinctness check; the trackers then store the top three values by position rather than the top three distinct values.
• What if you need the K-th largest instead of the third? – maintain a min-heap of size K; push each element, evict the smallest once the heap exceeds K, and return the heap root at the end for O(n log K) total time.
• What if you need the K-th largest in the average case faster than O(n log K)? – use the Quickselect algorithm with a random pivot for expected O(n) time, trading determinism for speed.
• What if the array arrives as an unbounded stream? – keep the same three trackers and the same cascading update rules; termination comes from end-of-stream rather than array length, and memory stays O(1).
• What if the array has billions of elements across many machines? – compute the local top three on each shard, then merge the per-shard triples with a single pass of the same algorithm; the shard step is embarrassingly parallel.

Conclusion

Finding the third largest element is the first step up from the two-tracker pattern, and it rewards getting the cascading demotion right. Three trackers, strict comparisons on both sides of each tier, and a bottom-up assignment order turn a deceptively simple problem into a clean O(n) solution that handles duplicates, negatives, and short arrays without surprises.

Try adapting the program to return the top K distinct values, or to generalize the three-tracker pattern into a single array of trackers for arbitrary K. You can learn more about array problems like this one on our Arrays category page.