Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Keep `first` and `second` (both very small initially). For each x: if x > first, shift first into second and set first = x; else if x > second and x != first, update second.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you track top-K in one pass and handle duplicates and negatives correctly.
Where candidates slip
Losing the runner-up by not demoting, or 0-seeding the trackers.
How to stand out
Clarify the distinct-vs-duplicate definition before coding.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Track top two
1Hint 1Explore hintHide hint
Do you need to sort, or can you remember just the top two?
2Hint 2Explore hintHide hint
On beating the best, demote the old best to the runner-up.
3Hint 3Explore hintHide hint
Decide whether duplicates of the max count — skip them for 'second distinct'.
A · Core idea
Track the top two values in a single pass: a first (largest) and second (runner-up). For each element, either it beats first (so the old first demotes to second and the element becomes the new first), or it slots between them (updating second). O(n), no sort.
Why demote, not overwrite. When a new value exceeds first, the previous first is now the second-largest, so you must shift it into second before overwriting first. Forgetting this loses the runner-up.
Handling duplicates of the max. 'Second largest' usually means the second distinct value, so when an element equals first you skip it for second (the x != first guard). For [10, 10, 5] that yields 5, not 10.
Why seed with −∞. Initialising both trackers to the smallest possible value (Long.MIN / −inf) ensures the first real elements populate them correctly, even for all-negative arrays. Sorting also works (O(n log n)) but the one-pass tracker is the O(n) answer.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [3, 7, 2, 9, 4]3
3 > −∞
first=3, second=−∞7C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Sorting works (O(n log n)) but the one-pass top-two tracker is the O(n) answer interviewers want.
ComplexityO(n) time, O(1) space — one pass, at most two comparisons per element, O(1) state — beats the O(n log n) sort.
E · Edge cases and pitfalls6nums = [10, 10, 5] — Distinct second largest is 5; the x != first guard skips the duplicate 10.Explore edge casesHide edge cases
Edge cases handled
nums = [10, 10, 5]Distinct second largest is 5; the x != first guard skips the duplicate 10.nums = [1, 2]Second is 1.nums = [-3, -1, -2]Seeding with −∞ makes the all-negative case work; second is -2.
Pitfalls
- Overwriting first without demoting it into second.
- Initialising the trackers to 0 instead of −∞.
- Returning the max again when duplicates of the max exist.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int secondLargest(int[] nums) { long first = Long.MIN_VALUE, second = Long.MIN_VALUE; for (int x : nums) { if (x > first) { second = first;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
- Returning the largest when duplicates of the max exist.
- Initialising first/second to 0 instead of negative infinity.
Revise
Carry the pattern into the interview
Pattern to remember
Track top-two in one pass
Code pattern to memorize
if x>first: second=first; first=x elif x>second and x!=first: second=xRules to remember
- 1Seed both to −∞.
- 2Beat first → demote first to second.
- 3Skip x == first for distinctness.
Use this pattern when
- Top-K for small K without sorting
Choose another pattern when
- Large K — use a heap or quickselect
Interview takeaway
Top-K of small K is a running tracker, not a sort.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: Track top-two in one pass. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum in an ArrayThe single-tracker version.
- Kth Largest ElementComing soonGeneralises to a heap or quickselect.