AlgoViz
HomeArrays & Hashing

Second Largest Element

Easy

Track the best two, in one pass

Problem

Given an array of integers nums, return the second-largest element in the array. If the second-largest element does not exist, return -1.

In simple words

Track the top two different values as you scan — the runner-up is your answer.

The idea

Keep two running values, the largest and the runner-up, and update them together: when a new element beats the largest, the old largest becomes the runner-up. Skipping values equal to the current largest is what makes it the second *distinct* element.

The trick

  • Update in the right order or you will overwrite the largest before saving it.
  • Ignore duplicates of the maximum, or [5,5] wrongly reports 5.
  • One pass beats sorting: O(n) rather than O(n log n).
i
8
8
7
6
5
0
1
2
3
4
largest8
second–

Step 1 of 6. See 8: largest=8, second=–. Values: 8, 8, 7, 6, 5. Pointers: i at index 0. largest 8, second –.

1/6
Optimal
timeO(n)spaceO(1)
1largest = second = -infinity2for x in nums:3  if x > largest:4    second = largest; largest = x5  elif x < largest and x > second:6    second = x7return second == -infinity ? -1 : second

Input

array
[8, 8, 7, 6, 5]

Memory

i
= 0 [8]
second
–

Output

largest
8
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 4, 7, 7, 5]
Output:
5
Explanation:
The largest is 7, and the next distinct value is 5.

Example 2

Input:
nums = [10, 10, 10]
Output:
-1
Explanation:
All values are equal, so there is no second largest.

Example 3

Input:
nums = [1, 2]
Output:
1
Explanation:
The second largest of 1 and 2 is 1.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • nums may contain duplicate elements.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.