Problem statement

Given an array arr of positive integers, return the second largest distinct value in it.

If every element is the same — so no second distinct value exists — return -1.

Example 1

Input: arr = [12,35,1,10,34,1]
Output: 34
Explanation: The largest is 35 and the largest value strictly below it is 34.

Example 2

Input: arr = [10,10,10]
Output: -1
Explanation: Only one distinct value exists.

Example 3

Input: arr = [5,9]
Output: 5

Constraints

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 100000

Hints for Second Largest Element

1. Hint 1

   Sorting works, but a single pass is enough.

2. Hint 2

   Carry two running values — the best and the best-so-far below it.

3. Hint 3

   When a new maximum arrives, the old maximum becomes the runner-up. Ignore values equal to the current maximum entirely.

How to solve Second Largest Element

One pass suffices: track the largest value seen and the largest value strictly below it. Every new element either beats the leader, slots in between, or is irrelevant.

Approach

1. Initialise first and second to -1 — safe because every element is at least 1.
2. For each x: if x > first, the old first becomes second and x becomes first.
3. Otherwise, if x < first and x > second, then x is the new runner-up.
4. An x equal to first is skipped, which is what makes the answer distinct.

Why it works

The invariant after each step is that first is the maximum of the prefix and second is the maximum of the prefix values strictly less than first. Both update rules preserve it, so after the last element second is exactly the answer.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Sorting and taking arr[n-2] is wrong when the maximum repeats — [10,10,9] would answer 10.
• Skipping the x < first guard lets a duplicate maximum overwrite the runner-up.

Reference solution

Python

from typing import List

def getSecondLargest(arr: List[int]) -> int:
    first = -1
    second = -1
    for x in arr:
        if x > first:
            second = first
            first = x
        elif x < first and x > second:
            second = x
    return second

Java

public static int getSecondLargest(int[] arr) {
    int first = -1, second = -1;
    for (int x : arr) {
        if (x > first) {
            second = first;
            first = x;
        } else if (x < first && x > second) {
            second = x;
        }
    }
    return second;
}

C++

int getSecondLargest(vector<int>& arr) {
    int first = -1, second = -1;
    for (int x : arr) {
        if (x > first) {
            second = first;
            first = x;
        } else if (x < first && x > second) {
            second = x;
        }
    }
    return second;
}

JavaScript

var getSecondLargest = function(arr) {
    let first = -1, second = -1;
    for (let i = 0; i < arr.length; i++) {
        const x = arr[i];
        if (x > first) {
            second = first;
            first = x;
        } else if (x < first && x > second) {
            second = x;
        }
    }
    return second;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy