Given an array arr of positive integers, return the second largest element in it.
The second largest must be strictly smaller than the largest — if the maximum value appears more than once, those extra copies do not count as the runner-up. For arr = [10, 5, 10] the largest is 10 and the second largest is 5.
If no valid second largest exists (for example, when every value is identical), return -1.
Input: arr = [12, 35, 1, 10, 34, 1] Output: 34 The largest element is 35 and the next distinct value below it is 34.
Input: arr = [10, 5, 10] Output: 5 The largest is 10; ignoring its duplicate, the second largest is 5.
Input: arr = [10, 10, 10] Output: -1 Every value equals the largest, so no strictly-smaller second largest exists.
- 2 <= arr.size <= 10^5 - 1 <= arr[i] <= 10^5
Second Largest looks like a trivial follow-up to "find the maximum", but it hides a classic trap: duplicates of the champion must not claim the runner-up spot. It's the problem that teaches you to carry two running values at once and to be careful about strict inequality — a pattern that scales to top-k and to the median-of-a-stream family.
> and >= is the whole problem — the second largest must be strictly below the largest.-1) to mean "nothing found yet", so the no-answer case falls out for free.Given an array arr, return the largest value that is strictly smaller than the maximum. If no such value exists (every element is equal), return -1.
Worked example — arr = [12, 35, 1, 10, 34, 1]
largest second see 12 → 12>−1 12 −1 see 35 → 35>12 35 12 (old champion 12 slides to second) see 1 12 see 10 → 10>−? no change 12 see 34 → 34<35, 34>12 35 34 see 1 34 answer: 34 ✓
“Is the array guaranteed to have at least two elements?”
Here yes (size >= 2). With one element there is no runner-up at all.
“Are the values always positive?”
Yes (>= 1), which is why -1 is a safe "nobody yet" sentinel — no real value can collide with it.
“What if the largest value appears multiple times?”
Its duplicates do not count. In [10, 5, 10] the answer is 5, not 10.
“What if every element is identical, like [10, 10, 10]?”
There is no value strictly below the maximum, so return -1.
“What should I return when there is no second largest?”
-1 — confirm the sentinel the problem expects rather than throwing or returning the max.
“How large can the array be?”
Up to 10^5. A sort is fine, but a single linear pass is cleaner and faster.
A few quick questions first.
Does "second largest" mean a value strictly smaller than the maximum, so duplicate maxima don't count?
What should I return when there's no valid runner-up — is -1 the expected sentinel?
Are the values always positive?
Good. I'll sweep once, carrying the largest and the best value strictly below it.
This is the trap the problem is built around. "Delete the max, take the new max" fails on [10, 5, 10] — you'd delete one 10 and return the other. The second largest is defined by value, not position: it must be strictly less than the maximum, so every copy of the maximum is disqualified.
You don't need to know the whole ranking, only the top two. Carry largest and second. When you meet a new champion, the previous champion is exactly the new runner-up, so it slides down into second. One pass, two variables.
Check the new-champion case first: if the value beats largest, demote largest into second and install the new maximum. Only otherwise consider it for second — and then only if it is strictly less than largest and greater than second. Seed both with -1 so "no runner-up exists" needs no special-casing at the end.
| Sort & walk down | Two trackers | |
|---|---|---|
| Idea | Sort, step back from the top to the first smaller value | One sweep, carry largest + second |
| Time | O(n log n) | O(n) |
| Space | O(1) | O(1) |
The full code for both is in the Approaches selector below.
Key takeaway
To find a runner-up, carry the top two values in one O(n) pass and demote the old champion when a new one appears — but guard the strict inequality so duplicates of the maximum never claim second place, and use a sentinel so "no second largest" returns cleanly.