Find the Second Largest Element in an Array

Title: Find the Second Largest Element in an Array

In this guide, you’ll learn how to find the second largest element in an array using a single pass through the data. We’ll walk through the problem, build a clean linear-time solution in Java, trace it by hand on a fresh input, and then stress test it against the edge cases that trip candidates up during coding interviews.

The problem looks small, but it hides a few sharp corners around duplicates, negative numbers, and short arrays. By the end of this article you’ll have a program you can defend under follow-up questions and a mental checklist for every boundary input the interviewer might throw at you.

Understanding the Problem

Given an integer array, we want to return the second largest distinct value. For {10, 5, 10, 8, 3} the largest is 10 and the second largest is 8, not another 10. If every element is identical, no second largest exists and our program should raise an error rather than silently return a misleading value.

Two observations shape the solution. First, a single scan is enough: we only need to remember two numbers at any time, the current largest and the current secondLargest. Second, we must treat duplicates of the largest as already seen so they do not slide themselves into the runner-up slot.

Approach to Find the Second Largest Element

We can solve this in one linear pass by maintaining two running values. The algorithm steps are:

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

Java Program

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

public class SecondLargestElement {
    public static int findSecondLargest(int[] numbers) {
        if (numbers == null || numbers.length < 2) {
            throw new IllegalArgumentException("Array must contain at least two elements");
        }
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > largest) {
                secondLargest = largest;
                largest = numbers[i];
            } else if (numbers[i] > secondLargest && numbers[i] != largest) {
                secondLargest = numbers[i];
            }
        }
        if (secondLargest == Integer.MIN_VALUE) {
            throw new IllegalArgumentException("No distinct second largest element exists");
        }
        return secondLargest;
    }

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

Explanation of the Program

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

We seed both largest and secondLargest with Integer.MIN_VALUE so that any real integer in the array will beat the initial values. This matters when the array contains only negative numbers, where seeding with 0 would silently return the wrong answer.

Inside the loop, the first branch handles a new maximum. The previous maximum slides into the second slot before the current element takes the top, so no information is lost. The second branch is the subtle one: the check numbers[i] != largest is what makes the output the second largest distinct value. Drop that guard and a tie with the current maximum would overwrite the runner-up and corrupt the answer.

The final guard catches arrays that have a maximum but no distinct runner-up, like {7, 7, 7}. Rather than returning Integer.MIN_VALUE, which the caller might mistake for a real value, we surface the issue at the call site.

Step-by-Step Trace

Let’s run the algorithm on the input {8, 3, 8, 11, 5, 11}, which should finish with largest = 11 and secondLargest = 8. Each row below shows the state after that iteration completes.

Invariant: at the end of each iteration, largest holds the maximum of the elements seen so far and secondLargest holds the next-largest distinct value seen so far. Iterations 3 and 6 are the ones worth staring at; they are the duplicates of the current largest, and the != largest guard is what keeps them from corrupting the runner-up.

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 secondLargest = findSecondLargest(numbers);
System.out.println(secondLargest);
// Output: 34

The maximum 35 wins the top slot and 34 settles into the runner-up slot. The repeated 1 is harmless because it never beats either tracker.

Example 2: Array of Negative Numbers

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

An all-negative array is where seeding largest with 0 would quietly fail. Because we seeded with Integer.MIN_VALUE the first element wins the top slot and the algorithm proceeds correctly, returning -2.

Example 3: Repeated Largest Element

int[] numbers = {50, 50, 20, 40, 50};
int secondLargest = findSecondLargest(numbers);
System.out.println(secondLargest);
// Output: 40

Here the maximum 50 appears three times. The != largest guard prevents those duplicates from overwriting the runner-up, so secondLargest settles at 40 rather than at 50.

Common Mistakes to Avoid

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

• Sorting the whole array – solves the problem in O(n log n) when O(n) is possible, and interviewers notice. Keep two running trackers and make a single pass instead.
• Initializing to zero – fails on arrays containing only negative numbers because 0 is wrongly reported as a candidate maximum. Initialize both trackers to Integer.MIN_VALUE.
• Dropping the != largest guard – lets a duplicate of the current maximum overwrite the runner-up, so {50, 50, 40} returns 50 instead of 40. Keep the distinctness check in the else-if branch.
• Using >= instead of > on the first branch – demotes the current largest into the runner-up whenever a duplicate appears, which is wasted work and leaves secondLargest equal to largest. Use strict greater-than so duplicates fall through to the else-if.
• Silently returning Integer.MIN_VALUE for all-equal arrays – 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
• Single-element array
• Two-element array with equal values
• All identical elements
• All negative elements
• Largest element at index 0
• Largest element at the last index
• Multiple duplicates of the maximum
• 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 a constant amount of work per element. Space usage is O(1): only two integer trackers plus the loop index, 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 it mutates the input unless you copy it first. A heap-based approach using a PriorityQueue of size two is also possible but adds log-factor overhead for no real benefit on this problem.

One edge case worth calling out explicitly: an array that already contains Integer.MIN_VALUE. Our final guard checks secondLargest == Integer.MIN_VALUE to detect the no-distinct-runner-up case, which collides with a legitimate Integer.MIN_VALUE input value. In a production setting you would use a boolean flag or an OptionalInt return type 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 maximum should count as the second largest? – drop the != largest guard; the algorithm then returns the second element by position in the sorted order, allowing ties.
• What if the input is already sorted in ascending order? – scan from the end for the first value strictly less than the last element; the running trackers are unnecessary and the walk is O(n) worst case but typically O(1).
• What if you need the K-th largest rather than the second largest? – maintain a min-heap of size K, pushing each element and evicting the smallest; final heap root is the answer in O(n log K).
• What if the array arrives as an unbounded stream? – keep the same two trackers and update them per incoming value; termination comes from end-of-stream rather than array length, and memory stays O(1).
• What if the array is too large to fit in memory? – partition the input into chunks, compute the top two values per chunk independently, then merge the per-chunk pairs with the same algorithm; the chunk step is embarrassingly parallel.

Conclusion

Finding the second largest element rewards a careful single-pass algorithm over a sort-and-slice shortcut. Two trackers, a strict greater-than check, and a distinctness guard turn a deceptively simple problem into a clean O(n) solution that handles negatives, duplicates, and short arrays without surprises.

Try adapting the program to return the top K distinct values, or to work on a List<Integer> rather than a primitive array. You can learn more about array problems like this one on our Arrays category page.