Second Largest Number

Q: What is the time complexity of finding the second largest element?

The one-pass and two-pass methods both take O(n) time and O(1) extra space. Sorting first takes O(n log n) time. You cannot beat O(n) , because every value has to be read at least once.

BeginnerArrays and strings

+10

You get a list of integers nums. Return its second largest distinct value: the largest value that is strictly smaller than the maximum. Values can repeat, so for [5, 5, 3] the answer is 3, not 5. The list always holds at least two different values.

Function

secondLargest(nums: integer-array) → integer

numsinteger-array: the list of integers, with at least two distinct values
Returnsinteger: the largest value that is smaller than the maximum

Constraints

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums contains at least two distinct values.

Examples

Input: nums = [4, 9, 2, 7, 9]
Output: 7
Explanation: The maximum is 9. It appears twice, but a second copy of the maximum does not count, so the answer is the next value down, 7.

Input: nums = [-5, -1, -8]
Output: -5
Explanation: From largest to smallest the values are -1, -5, -8. The second largest is -5, even though it is negative.

Input: nums = [6, 6, 6, 3]
Output: 3
Explanation: Only two distinct values exist, 6 and 3. However many times 6 repeats, the second largest is 3.

+15 hidden tests on Submit

Follow-up

Can you return the third largest distinct value in one pass, with three variables and no sorting?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Two details make this harder than finding the maximum. The maximum can repeat, and a repeat must not be reported as the second largest. The answer can be negative, so a variable that starts at 0 gives a wrong answer on an all-negative list. Tracking the top two distinct values in one pass, with strict comparisons, handles both.

Sort and step down past the maximum

Intuition

Sort a copy from smallest to largest. The maximum sits at the end, possibly several times in a row. Walk left from the end past every copy of the maximum; the first different value is the second largest. For [6, 6, 6, 3] the sorted copy is [3, 6, 6, 6]: you skip three 6s and land on 3.

Returning the second to last element is the classic mistake here. For [4, 9, 2, 7, 9] it returns 9, the maximum again. The walk cannot run off the front, because the list holds at least two distinct values.

The answer is right, but sorting orders every value when you only care about the top two. It costs O(n log n) time and the copy O(n) memory.

Algorithm

Copy nums and sort the copy from smallest to largest.
Start an index i at the last position.
While the value at i equals the maximum, move i one step left.
Return the value at i.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

Two passes

Intuition

Split the job in two. The first pass finds the maximum, as in Find the Largest Number. The second pass looks for the largest value that is strictly smaller than that maximum. For [4, 9, 2, 7, 9] the first pass finds 9, and the second pass skips both 9s and keeps the biggest of 4, 2 and 7, which is 7.

Start second below every value the list can hold, such as the smallest integer your language has. The list has at least two distinct values, so some value is smaller than the maximum and always replaces that start.

Each pass is a running maximum, so the total is O(n) time and O(1) space. The cost is reading the list twice, which is impossible when the values arrive one by one and are gone after you read them.

Algorithm

Loop over nums once and store the maximum in largest.
Set second below every allowed value.
Loop again. For each x with x < largest and x > second, set second to x.
Return second.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

One pass tracking the top two

Intuition

Keep two variables, largest and second, for the top two distinct values seen so far. Each new value x falls into one of three cases. If x is bigger than largest, the old largest drops to second place and x takes the top. If x lies strictly between second and largest, it becomes the new second. In every other case nothing changes.

The strict comparisons are what handle duplicates. For [4, 9, 2, 7, 9]: largest becomes 4, then 9 with second = 4. 2 changes nothing, 7 lies between 4 and 9 so second = 7, and the last 9 equals largest, so it is skipped. The answer is 7.

Start both variables below every possible value. Starting both at 0 returns 0 for [-5, -1, -8], because no value ever beats 0. Because the list holds two distinct values, second always ends on a real value from the list.

Algorithm

Set largest and second below every allowed value.
Loop over every value x in nums.
If x > largest, move largest into second and set largest to x.
Otherwise, if x < largest and x > second, set second to x.
After the loop, return second.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

Pitfalls and edge cases

Most wrong answers come from duplicates of the maximum or from negative values.

Returning the second to last element of the sorted list. With a repeated maximum, as in [4, 9, 2, 7, 9], that is the maximum again.
Starting the variables at 0. On [-5, -1, -8] no value beats 0, and you return 0, a number that is not in the list.
Writing x >= largest in the first case. A second 9 then pushes the first 9 into second, and you return 9.
Updating second only when a new maximum appears. In [10, 20, 15], the 15 never reaches second, and you return 10.
Removing duplicates with a set and then sorting. It works, but it spends O(n) memory and O(n log n) time on a job one pass does.

Frequently asked questions4

How do you find the second largest number in an array in one pass?

Keep the largest and the second largest distinct values seen so far. When a value beats the largest, the old largest moves to second place. When a value lies strictly between the two, it replaces the second. After one pass, the second variable holds the answer.

What is the time complexity of finding the second largest element?

The one-pass and two-pass methods both take O(n) time and O(1) extra space. Sorting first takes O(n log n) time. You cannot beat O(n), because every value has to be read at least once.

How do duplicates affect the second largest element?

This problem asks for the second largest distinct value, so copies of the maximum are skipped. For [9, 9, 7] the answer is 7. Some versions of the question count positions instead and would answer 9, so check which one is meant before you code.

What should you return when there is no second largest value?

Here it cannot happen: the list always holds two distinct values. In general, a list such as [4, 4, 4] has no answer, and you would return a marker such as -1 or null or raise an error. You can detect the case when second still holds its starting value after the loop.

Python

def secondLargest(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [4, 9, 2, 7, 9]

Expected

Second Largest Number

Function

Constraints

Examples

Hints

Solution

Sort and step down past the maximum

Two passes

One pass tracking the top two

Pitfalls and edge cases

Frequently asked questions4

Similar problems