Start learning free

LESSON 329 OF 344 · GREEDY

Find Second Largest in Python: One Pass with Two Variables

Practice O(n) Read the full explanation

Given an array of integers, return the second largest value.

Example:

Input: nums = [2, 7, 11, 8, 11, 8, 3, 11]
Output: 8
Explanation: The maximum value is 11. The second largest value is 8.

Note:

You may assume the array contains at least two distinct values.


Follow up:

Could you solve this in one pass without sorting?


STEP 1 OF 7
    Ctrl + Enter to check

    PYTHON · GREEDY

    Find Second Largest in Python, explained

    Problem overview

    The method secondLargest receives a list nums of integers and returns the second largest distinct value. The input is guaranteed to contain at least two distinct values.

    In the example, nums = [2, 7, 11, 8, 11, 8, 3, 11]. The largest value is 11, which appears three times. The next distinct value below it is 8, so the answer is 8, not 11. A second copy of the maximum does not count as the second largest.

    Approach: track the top two in a single pass

    The obvious solution sorts the list in descending order and picks the second item, but duplicates make it awkward, and sorting costs O(n log n). The statement's follow-up asks for one pass without sorting.

    You can do it by remembering only two values while you walk through the list: the largest seen so far and the runner-up. Each new number does one of three things:

    • It beats the current maximum. The old maximum is now the runner-up, and the new number is the maximum.
    • It is smaller than the maximum but larger than the runner-up. It becomes the new runner-up.
    • Otherwise, it changes nothing: it is equal to the maximum, or no better than the runner-up.

    Both variables start at negative infinity, so any real number beats them and the first iteration needs no special case. Negative infinity is also a good starting point for lists of negative numbers, which a starting value of 0 would handle wrongly.

    Here is the example traced. The pair is written as (max_val, second):

    • Start: (-inf, -inf).
    • 2 beats the maximum: (2, -inf).
    • 7 beats it: (7, 2).
    • 11 beats it: (11, 7).
    • 8 is below 11 and above 7: (11, 8).
    • 11 equals the maximum, so nothing changes. The same is true for the last 11.
    • The remaining 8 and 3 are not above the runner-up 8, so nothing changes.

    The result is 8.

    Step by step

    1. Declare max_val and second, both as float('-inf'). This value compares smaller than every integer.
    2. Loop over nums with the variable num.
    3. Test for a new maximum with num > max_val. Use a strict comparison.
    4. Demote, then replace. Inside that branch, first copy max_val into second, and only then store num in max_val. The order matters, because after the second assignment the old maximum is lost.
    5. Test for a new runner-up in an elif: num must be below max_val and above second. The first condition keeps copies of the maximum out of second place, and the second keeps a worse number from replacing a better runner-up.
    6. Update second to num in that branch.
    7. Return second after the loop.

    The solution in Python

    class Solution:
    def secondLargest(self, nums: List[int]) -> int:
        max_val = float('-inf')
        second = float('-inf')
        for num in nums:
            if num > max_val:
                second = max_val
                max_val = num
            elif num < max_val and num > second:
                second = num
        return second

    The Python details worth a closer look:

    • float('-inf') works with integers. Python compares an int and a float directly, so 5 > float('-inf') is True. No conversion is needed.
    • The return value can be a float. If the input had fewer than two distinct values, second would still be -inf when the loop ends. The guarantee in the statement rules this out, so for valid input the function returns an integer.
    • Chained elif. The elif runs only when the if condition was false, so a number never updates both variables in the same iteration.
    • Why not a swap trick? Python allows second, max_val = max_val, num in one line, which also gets the order right, but two separate assignments make the "copy first" rule visible.
    • Why not sorted(nums)[-2]? With duplicates of the maximum, the second-to-last item of the sorted list is the maximum again. Using sorted(set(nums))[-2] fixes that, at the cost of a sort and an extra set.

    Complexity

    Time: O(n). The loop visits each element once and does a constant number of comparisons.

    Space: O(1). Only two variables are kept, whatever the size of the list.

    Edge cases and common mistakes

    • Duplicates of the maximum. For [5, 5, 1] the answer is 1. The test num < max_val stops the second 5 from becoming the runner-up.
    • All negative numbers. For [-3, -1, -2] the answer is -2. Starting both variables at 0 would give a wrong answer here, which is why negative infinity is used.
    • Only two elements. [1, 2] returns 1.
    • Ascending or descending input. Both are fine. In ascending order the runner-up is replaced by every new maximum, and in descending order it is set by the second element.
    • Overwriting in the wrong order. Setting max_val = num before second = max_val makes both variables equal to num.
    • Using >= in the first test. A repeated maximum would then copy the maximum into second, which returns the maximum itself.
    • No second distinct value. [3, 3] would return -inf. The statement promises this never happens.

    Testing

    • [2, 7, 11, 8, 11, 8, 3, 11] gives 8.
    • [5, 5, 1] gives 1.
    • [-3, -1, -2] gives -2.
    • [1, 2] gives 1.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free