0628EasyArraySorting

Third Highest Distinct Reading

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A weather post logs one temperature change per day of a survey into the list readings. A change may be positive, zero or negative, and the same change can be logged on several days.

Collapse repeats so that each value present in readings is considered once, then rank those values from largest down. Return the value in third place. When the survey holds fewer than three different values, return the largest value instead.

Examples

Example 1

Input: readings = [4, 9, -6, 4, 12]
Output: 4

The different values logged are 12, 9, 4 and -6. Ranking them from largest down gives 12 first, 9 second and 4 third, so 4 is returned.

Example 2

Input: readings = [7, 7, 7]
Output: 7

Every day logged the same change, so the survey holds one different value. That is fewer than three, so the largest value 7 is returned.

Example 3

Input: readings = [2147483647, 0, -2147483648]
Output: -2147483648

All three values differ. Ranked from largest down they are 2147483647, 0 and -2147483648, so third place holds -2147483648.

Constraints

1 <= readings.length <= 10^4
-2^31 <= readings[i] <= 2^31 - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def third_max(readings: list[int]) -> int:

Java

public int thirdMax(int[] readings)

The intended approach

Time O(n) — one pass, with a fixed amount of work per reading.Space O(1) — three slots regardless of input size.

Walk the list once holding three slots that always contain the three largest values met so far, biggest first. A value already sitting in a slot is skipped, so repeats cannot fill two slots. Otherwise the value is inserted at the first slot it beats and the slots below it shift down. Each slot starts as None rather than as a very small number, because -2147483648 is a legal reading and a numeric placeholder could not be told apart from it. If the third slot is still empty at the end, fewer than three distinct values were logged and the first slot is returned.

Pythonentry point: third_max

def third_max(readings):
    # O(n) time, O(1) extra space: a single pass keeps the three largest
    # distinct values seen so far, ordered top[0] > top[1] > top[2]. None marks
    # a slot no distinct value has reached yet, which keeps a genuine reading of
    # -2147483648 from being mistaken for an empty slot.
    top = [None, None, None]
    for v in readings:
        if v in top:
            continue
        if top[0] is None or v > top[0]:
            top = [v, top[0], top[1]]
        elif top[1] is None or v > top[1]:
            top = [top[0], v, top[1]]
        elif top[2] is None or v > top[2]:
            top = [top[0], top[1], v]
    if top[2] is None:
        return top[0]
    return top[2]

The obvious version

Drop the list into a set to collapse repeats, sort the result in descending order, and index the third entry, falling back to the first entry when the sorted list is shorter than three.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_third_max(readings):
    distinct = sorted(set(readings), reverse=True)
    if len(distinct) < 3:
        return distinct[0]
    return distinct[2]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in