L2 · Working engineerLists & arrays~8 min · 8 tests#1

Second Largest Number Without Sorting

Find the second-highest distinct number in a Python list in one pass, without sort(). Run it in the browser, check edge cases, and measure O(n).

The problem

Given a list of integers, return the second-highest distinct value without sorting the list.

Duplicates of the maximum do not count: in [10, 20, 20] the answer is 10.
If there is no second distinct value (empty list, one element, all equal), return None.

Examples

Example 1

Input

second_highest([10, 5, 20, 8, 20, 15])

Expected output

Example 2
Input
```
second_highest([1, 2])
```
Expected output
```
1
```
Example 3 · all equal
Input
```
second_highest([7, 7, 7])
```
Expected output
```
None
```

+ 5 hidden tests on Submit — empty list, one element, negatives, duplicates of second.

Edge cases to ask about

Empty list
Single element
All values equal
Only negative numbers

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · second_highest

def second_highest(nums):
    """Return the second-highest distinct value, or None."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

Measure it

Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Sort the distinct values	O(n log n)	O(n)	set() then sorted(); index 1. Correct, but sorting does far more work than the question needs.
bestSingle pass with two trackers	O(n)	O(1)	Keep the best and second-best seen so far; a new maximum demotes the old one to second.

Walkthrough of the optimal approach (try it yourself first)

Walk the list once with two trackers, first and second.

A value bigger than first becomes the new first, and the old first slides down to second.
A value that is not equal to first but beats second replaces second.
Equal-to-max values are ignored, which is what makes the answer distinct.

Using None as "not seen yet" (instead of 0 or -inf) keeps negative numbers correct and gives the None answer for free.

Complexity: O(n) time, O(1) space. Every element is looked at exactly once and the loop keeps two variables, no matter how long the list is.

Reveal the reference solution

def second_highest(nums):
    first = second = None
    for x in nums:
        if first is None or x > first:
            first, second = x, first
        elif x != first and (second is None or x > second):
            second = x
    return second

The brute force, for comparison

def second_highest(nums):
    distinct = sorted(set(nums), reverse=True)
    return distinct[1] if len(distinct) > 1 else None

Follow-ups interviewers ask

Generalise it to the k-th largest. What data structure keeps it O(n log k)?
What changes if duplicates DO count as separate places?

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Second Largest Number Without Sorting in Python?

The optimal solution runs in O(n) time and O(1) auxiliary space. Every element is looked at exactly once and the loop keeps two variables, no matter how long the list is.

What is the brute-force approach, and how do you optimise it?

Sort the distinct values: O(n log n) time, O(n) space. set() then sorted(); index 1. Correct, but sorting does far more work than the question needs. Single pass with two trackers: O(n) time, O(1) space. Keep the best and second-best seen so far; a new maximum demotes the old one to second.

What follow-up questions do interviewers ask about Second Largest Number Without Sorting?

Generalise it to the k-th largest. What data structure keeps it O(n log k)? What changes if duplicates DO count as separate places?