Problem 0.2 · Java for DSAEasy

Second Largest Element

What it teaches: Keeping a small running state (the largest and second largest so far) in one pass, and handling duplicates and tiny inputs carefully.

The problem

Given an integer array nums, return the second largest distinct value. If there isn't one (all values equal, or fewer than two elements), return -1.

Example 1

Input: nums = [12, 35, 1, 10, 34, 1]
Output: 34

Example 2

Input: nums = [10, 10, 10]
Output: -1

All values are the same, so there's no second distinct value.

Example 3

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

Constraints

0 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹

Pattern clues in the wording

→ "Largest" and "second largest": a summary of everything seen so far
→ Sorting would work but costs O(n log n); one pass with two variables is enough

These clues point to Running State in One Pass: Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int secondLargest(int[] nums) {
        int first = -1, second = -1;
        // update first and second for each value
        return second;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [12,35,1,10,34,1]	34
2	nums = [10,10,10]	-1
3	nums = [5,9]	5
4	nums = []	-1

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Sort, then scan from the end · O(n log n)2. Optimal: one pass with two variables · O(n)

Sort, then scan from the end

Time O(n log n) Space O(1) extra (sorting in place)

Sort ascending. The largest is at the end; walk backwards past copies of it, and the first smaller value is the answer.

Approach 1

import java.util.Arrays;

class Solution {
    public int secondLargest(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] != nums[n - 1]) return nums[i];
        }
        return -1;
    }
}

Verdict: Simple and correct, but sorting does more work than needed, and it changes the input order.

Optimal: one pass with two variables

Time O(n) Space O(1)

Walk the array once, keeping first and second. Start both at −1 (all values are non-negative, so −1 means "not found yet").

For each x: if x > first, shift first down to second and set first = x. Else if x < first and x > second, set second = x. If x == first, do nothing, so duplicates of the maximum don't count.

▶ Dry run: Tracking the top twonums = [12, 35, 1, 10, 34, 1]

↑i

State(vars)

first = 12second = -1

Step 1/612 > first (−1): it becomes first; old first (−1) moves to second.

Approach 2

class Solution {
    public int secondLargest(int[] nums) {
        int first = -1, second = -1;       // -1 means "none yet" (values are >= 0)
        for (int x : nums) {
            if (x > first) {
                second = first;
                first = x;
            } else if (x < first && x > second) {
                second = x;
            }
        }
        return second;
    }
}

Verdict: One pass, two variables, input untouched. This is the answer.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty array or one element → −1
All equal → −1
Largest value repeated, e.g. [5, 5, 3] → 3
Second largest appears before the largest, e.g. [9, 10]

Mistakes people make

Using x >= first in the first branch: a duplicate of the maximum would push the max into second, giving the max again as the answer.
Forgetting the x < first check in the second branch, so duplicates of first become second.
Starting both at 0 when 0 is a valid value: then [0, 0] would wrongly return 0.

Interview

Follow-up questions

What if values can be negative?

How would you find the kth largest distinct value?

Command Palette