Find Second Largest Element in an Array in Java

What is the Second Largest Element in an Array?

Finding the second largest element sounds like a small variation on finding the largest, but it's actually one of the most revealing interview questions in Java because a huge number of candidates default to sorting the array (an O(n log n) approach) when an O(n) single-pass solution exists.

This article walks through the optimal algorithm, the tricky duplicate-handling logic, and every edge case worth knowing.

Problem Statement

Given an array like:

{10, 45, 23, 89, 67}

The largest element is 89, and the second largest is 67.

The goal is to find the second largest value without fully sorting the array, ideally in a single traversal.

Why Sorting Is Not the Best Approach

The most obvious (and most commonly proposed by beginners) solution is:

Arrays.sort(numbers);
int secondLargest = numbers[numbers.length - 2];

This works, but it costs O(n log n), which is far more than necessary for a problem that only requires comparing values—not fully ordering them.

Interviewers specifically ask this question to see whether you recognize that a smarter O(n) approach exists.

Optimal Single-Pass Algorithm

public class SecondLargestElement {

    public static void main(String[] args) {

        int[] numbers = {10, 45, 23, 89, 67};

        int largest = numbers[0];
        int secondLargest = Integer.MIN_VALUE;

        for (int i = 1; i < numbers.length; i++) {

            if (numbers[i] > largest) {

                secondLargest = largest;
                largest = numbers[i];

            } else if (numbers[i] > secondLargest && numbers[i] != largest) {

                secondLargest = numbers[i];
            }
        }

        System.out.println("Second Largest Element: " + secondLargest);
    }
}

This solution:

• Runs in a single O(n) pass.

• Uses only O(1) extra space.

• Does not require sorting.

Step-by-Step Explanation

Initialization

largest starts as the first element.

secondLargest starts as Integer.MIN_VALUE, guaranteeing that any real value in the array will be considered greater during the first comparison.

Main Loop

For each element:

• If the current element is greater than largest:

  • The old largest becomes secondLargest.

  • largest is updated.

• Otherwise, if the current element is greater than secondLargest and is not equal to largest:

  • Update secondLargest.

Why the != largest Check Matters

Without this condition, a duplicate of the largest value could incorrectly overwrite secondLargest.

This check ensures duplicates of the maximum value are not considered the second largest when distinct values are required.

Handling Duplicates Correctly

Consider the array:

{10, 10, 8, 5}

• Largest = 10

• Second Largest = 8

The condition:

numbers[i] != largest

prevents another 10 from becoming the second largest.

If your problem definition treats duplicates as valid (second largest by position rather than distinct value), remove this condition.

Always clarify this assumption during interviews.

Internal Working (Memory View)

For the array:

{10, 45, 23, 89, 67}

Final Result

largest = 89
secondLargest = 67

Real-Life Analogy

Think of a class ranking system.

There is a topper and a second topper.

• If a new student scores higher than the topper:

  • The topper becomes second.

  • The new student becomes first.

• If a student scores higher than the second topper but lower than the topper:

  • They become the new second topper.

This is exactly how the algorithm updates largest and secondLargest.

Best Practices

• Initialize secondLargest with Integer.MIN_VALUE.

• Validate that the array contains at least two elements.

• Clearly define whether duplicates should count.

• Prefer the O(n) solution instead of sorting during interviews.

Common Mistakes

• Forgetting the != largest check when duplicate maximum values exist.

• Initializing secondLargest to 0, which fails for negative numbers.

• Not validating the array length.

• Using sorting instead of the optimal single-pass approach.

Expert Tips

• The same promotion/demotion pattern can be extended to find the k-th largest element.

• Always mention your assumptions about duplicate values during interviews.

• For repeatedly finding the top k elements, use a Min Heap (Priority Queue).

Edge Cases

if (numbers == null || numbers.length < 2) {
    throw new IllegalArgumentException(
        "Array must contain at least two elements");
}

Null Array

Should be checked and rejected.

Array with Fewer Than Two Elements

There is no valid second largest value.

All Elements Identical

Depending on the requirements, there may be no distinct second largest value.

Comparison Table

Frequently Asked Questions

What is the time complexity of the optimal algorithm?

O(n) because the array is traversed only once using constant extra space.

Why initialize secondLargest with Integer.MIN_VALUE instead of 0?

Because the array may contain negative numbers.

Using 0 would produce incorrect results.

How do duplicates affect the result?

Without the != largest condition, duplicate maximum values could incorrectly become the second largest.

What if the array has only one element?

There is no valid second largest value.

The program should throw an exception.

Is sorting an acceptable solution?

Yes, it works correctly.

However, it is less efficient (O(n log n)) than the optimal O(n) solution and is generally considered suboptimal in interviews.

Can I use a TreeSet?

Yes.

TreeSet<Integer> automatically removes duplicates and keeps elements sorted.

You can retrieve the second largest value using methods such as pollLast() or similar navigation methods.

How can I find the k-th largest element?

Use a Min Heap (Priority Queue) of size k.

This is the standard efficient solution for the generalized problem.

What if all elements are the same?

There is no distinct second largest value.

Handle this case by returning a sentinel value or throwing an exception, depending on the project requirements.