Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Find the Second Largest Element in an Array

Track the two largest distinct values in one pass without sorting the array.

EasyArraysPattern: array traversal, running answer

Problem statement

Given an integer array, return the second largest distinct value. Return null when a second distinct value does not exist.

For [7, 2, 7, 5], the answer is 5.

Constraints & requirements

INPUT
An integer array with possible duplicates
RETURN
Second largest distinct value, or null
TARGET
One pass without sorting

Examples 3 test cases

  1. Example 1 Duplicate maximum

    Input
    [7, 2, 7, 5]
    Output
    5

    Checks that the answer must be distinct.

  2. Example 2 Two values

    Input
    [2, 9]
    Output
    2

    Checks the smallest successful input.

  3. Example 3 No second value

    Input
    [4, 4, 4]
    Output
    null

    Checks the missing-answer contract.

Hints Optional

Hints become more specific one step at a time.
01Keep only what the answer needs

You do not need the full sorted order. Two running values are enough.

02Handle a new largest carefully

When a value becomes the new largest, the previous largest becomes the second largest.

03Respect distinctness

A value equal to the current largest must not replace the second largest.

How to think before coding

First solve the easier question: what is the maximum? A second scan could then find the greatest value strictly below it. Combine those scans by keeping both candidates. When a new largest arrives, demote the old largest before overwriting it. Otherwise update only the runner-up, and ignore equal maxima. Use null for a missing candidate because every int value may be legitimate.

Brute force and the improvement

Sort, then walk backward past copies of the maximum: O(n log n) time. Copying first preserves the input but needs O(n) extra space. Or make two scans: find the maximum, then the greatest value strictly below it. That also takes O(n) time and O(1) extra space, with two passes rather than one.

Intuition

Sorting works, but it costs O(n log n). We only need the two best distinct values, so keep them while scanning.

When a new largest value appears, the old largest becomes second largest. Otherwise, the current value may fit between them.

Java solution

Java
public static Integer secondLargest(int[] values) {
    // Fewer than two values cannot provide two distinct candidates.
    if (values == null || values.length < 2) {
        return null;
    }

    // Null means missing; a numeric sentinel could be valid input.
    Integer largest = null;
    Integer second = null;

    for (int value : values) {
        // A new maximum pushes the old maximum down into second place.
        if (largest == null || value > largest) {
            second = largest;
            largest = value;
        // Ignore duplicate maxima; only a distinct better runner-up qualifies.
        } else if (value < largest && (second == null || value > second)) {
            second = value;
        }
    }
    return second; // Null means no second distinct value was found.
}

Dry run

Numbered illustrated dry run for Find the Second Largest Element in an Array; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For [7, 2, 7, 5], both candidates start as null.

Read Decision Largest Second distinct
7 First candidate becomes largest 7 null
2 Smaller than 7: first runner-up 7 2
7 Duplicate maximum: ignore 7 2
5 Between 2 and 7: improve runner-up 7 5

Return 5. Two occurrences of 7 do not make it the second distinct value.

Complexity

Time is O(n). Extra space is O(1).

Common mistakes

  • Treating a duplicate of the largest value as the second largest distinct value
  • Using a fixed sentinel such as Integer.MIN_VALUE without thinking about valid input values
  • Sorting even though the original order may need to stay unchanged

Practice next

Next lessonCheck Whether an Array Is Sorted

Practice another one-pass invariant.

Back to Arrays →