easyArray ProblemsJava

Find the Third Largest Element in an Array

Find the third largest distinct value in an array in a single pass, without sorting.

Quick Answer

Keep three variables — first, second and third — for the three largest distinct values, all starting at Integer.MIN_VALUE. Scan once: when a value beats first, cascade first down to second and second down to third; otherwise slot it into second or third if it fits and is not equal to a bigger tracked value. This is O(n) with no sorting.

Problem Statement

Given an array of integers, find the third largest distinct value. The largest and second largest are the two biggest distinct values; the third largest is the next one below them.

Sorting works but is O(n log n). Instead, track the three largest distinct values as you scan the array a single time, then return the third.

Input: An array of integers arr with at least three distinct values.

Output: The third largest distinct integer in the array.

Examples

Example 1
Input:  [10, 5, 20, 8, 15]
Output: 10

Sorted descending distinct: 20, 15, 10 — the third is 10.

Example 2
Input:  [3, 1, 4, 1, 5, 9, 2, 6]
Output: 5

Distinct descending: 9, 6, 5 — duplicates of 1 collapse and the third largest is 5.

Constraints

  • 1 <= arr.length <= 10^6
  • Elements may be negative, zero, or duplicated

Think Before You Code

Reveal the questions to ask yourself first
  • Can you maintain the top three values in the same loop that reads the array?
  • What starting values guarantee real elements replace the placeholders?
  • How do you make sure duplicates do not fill more than one of the three slots?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
You do not need to sort. Three running variables hold the three largest distinct values.
Hint 2
Initialise `first`, `second` and `third` to `Integer.MIN_VALUE`, then cascade updates as you scan.
Hint 3
When an element beats `first`, push `first`->`second` and `second`->`third` before storing it. Use `!=` checks against already-tracked values so duplicates do not occupy two slots.

Approach

Reveal the step-by-step approach

Walk the array once, cascading the three largest distinct values.

  1. Set first = second = third = Integer.MIN_VALUE.
  2. For each element x:
    • If x > first: third = second; second = first; first = x.
    • Else if x != first && x > second: third = second; second = x.
    • Else if x != first && x != second && x > third: third = x.
  3. If third is still Integer.MIN_VALUE, there are not three distinct values.
  4. Otherwise return third.

The != guards keep the three tracked values distinct, so repeated numbers cannot claim more than one of the slots.

Dry Run

Walk through the example step by step

Scanning [10, 5, 20, 8, 15]:

x  | rule                  | first | second | third
---+-----------------------+-------+--------+------
10 | 10 > MIN -> first     | 10    | MIN    | MIN
5  | 5 > second(MIN)       | 10    | 5      | MIN
20 | 20 > 10 -> cascade    | 20    | 10     | 5
8  | 8 > third(5), distinct| 20    | 10     | 8
15 | 15 > second(10)       | 20    | 15     | 10
------------------------------------ answer = 10

Solution

Reveal the full Java solution
public class ThirdLargest {
    public static int thirdLargest(int[] arr) {
        long first = Long.MIN_VALUE;
        long second = Long.MIN_VALUE;
        long third = Long.MIN_VALUE;
        for (int x : arr) {
            if (x > first) {
                third = second;
                second = first;
                first = x;
            } else if (x != first && x > second) {
                third = second;
                second = x;
            } else if (x != first && x != second && x > third) {
                third = x;
            }
        }
        if (third == Long.MIN_VALUE) {
            throw new IllegalArgumentException("Fewer than three distinct elements");
        }
        return (int) third;
    }

    public static void main(String[] args) {
        System.out.println(thirdLargest(new int[]{10, 5, 20, 8, 15}));       // 10
        System.out.println(thirdLargest(new int[]{3, 1, 4, 1, 5, 9, 2, 6})); // 5
    }
}

The three largest distinct values can be maintained together because a new maximum always demotes the previous maximum to second and the previous second to third. Using long placeholders lets Integer.MIN_VALUE itself appear as a real array value without being confused with the "not yet set" sentinel.

Time: O(n)Space: O(1)

Common Mistakes

  • Seeding the trackers from arr[0] instead of a minimum sentinel, which breaks the cascade logic.
  • Omitting the `!=` guards, so a repeated maximum fills both first and second slots.
  • Assuming the array always has three distinct values and never checking for that case.

Edge Cases to Test

  • Fewer than three distinct values, e.g. [4, 4, 2] — no third largest exists.
  • Array containing Integer.MIN_VALUE as a real element.
  • All negative numbers, e.g. [-1, -5, -3, -2], where the third largest is -3.

Interview Follow-Ups

  • How would you generalise this to the k-th largest element?
  • Would a min-heap of size k be cleaner for larger k? What is its complexity?
  • How does the logic change if duplicates should count toward the ranking?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us