Second Largest Element in an Array

Problem Overview

Given an array of distinct integers, find the second largest value in a single pass, without sorting.

Why solve this?

A direct extension of tracking one running maximum — this forces you to track two running values at once, the same shape you'll reuse for running-minimum and Kadane's-style problems.

Pattern Recognition

Whenever a problem asks for the Nth best value with N small and fixed, think about tracking N running candidates in one pass instead of sorting the whole array.

Prerequisites

• No prior lessons required.

Hints

1. Sorting works but costs O(n log n) — a single pass can do it in O(n).
2. Track two variables: the largest value seen so far, and the second largest.
3. When a new value beats the current largest, the old largest becomes the new second largest before you update.

Approach

Track two running values, largest and secondLargest, both starting below any possible input value. Scan the array once: if the current value beats largest, the old largest becomes the new secondLargest before largest is updated; otherwise, if it beats only secondLargest, update just that. One pass, two comparisons per element.

Code

class Solution {
    public int secondLargest(int[] nums) {
        long largest = Long.MIN_VALUE, secondLargest = Long.MIN_VALUE;
        for (int num : nums) {
            if (num > largest) {
                secondLargest = largest;
                largest = num;
            } else if (num > secondLargest) {
                secondLargest = num;
            }
        }
        return (int) secondLargest;
    }
}

Related Problems

• Reverse an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy
• Maximum Consecutive Oneseasy