Module 02 · Hash Maps, Sets, and Frequency State

016. Most Frequent with Earliest Tie

Bridge · Download this solution · All solutions and shared helpers

Problem

Return the most frequent integer, breaking ties by its first appearance in nums. Empty input returns None. Frequency is measured over the whole list, not merely the prefix at which a value first becomes a temporary leader.

Examples

Example 1

most_frequent_earliest([2, 1, 2, 1])
=> 2

Two and one tie; two appeared first.

Example 2

most_frequent_earliest([])
=> None

No candidate exists.

Example 3

most_frequent_earliest([9, 1, 1, 9])
=> 9

A temporary lead by one must not decide the final tie.

Reveal the worked solution and reasoning

Why this mechanism works

First build complete frequencies. Then scan the original order and replace the answer only on a strictly larger final frequency. The first candidate at a tied frequency therefore stays ahead. Separating counting and selection makes the tie proof simpler than maintaining a moving leader.

State and boundaries

counts contains final frequencies. best is the earliest encountered value among those with the largest frequency examined so far.

Protocol

Handle empty input.
Build frequencies.
Seed best from the first value.
Replace best only for a strictly greater final count.
Return best.

Visualization

input: 2 1 2 1
final: count(2)=2, count(1)=2
first encounter wins -> 2

Python implementation

def most_frequent_earliest(nums):
    if not nums:
        return None
    counts = {}
    for value in nums:
        counts[value] = counts.get(value, 0) + 1
    best = nums[0]
    for value in nums:
        if counts[value] > counts[best]:
            best = value
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

most_frequent_earliest([2, 1, 2, 1])

L2 most_frequent_earliest: if not nums:
nums=[2, 1, 2, 1]

L4 most_frequent_earliest: counts = {}
nums=[2, 1, 2, 1]; counts={}

L5 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={}; value=2

L6 most_frequent_earliest: counts[value] = counts.get(value, 0) + 1
nums=[2, 1, 2, 1]; counts={2:1}; value=2

L5 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={2:1}; value=1

L6 most_frequent_earliest: counts[value] = counts.get(value, 0) + 1
nums=[2, 1, 2, 1]; counts={2:1, 1:1}; value=1

L5 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={2:1, 1:1}; value=2

L6 most_frequent_earliest: counts[value] = counts.get(value, 0) + 1
nums=[2, 1, 2, 1]; counts={2:2, 1:1}; value=2

... 3 intermediate state changes omitted ...

L8 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={2:2, 1:2}; value=2; best=2

L8 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={2:2, 1:2}; value=1; best=2

L8 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={2:2, 1:2}; value=2; best=2

L8 most_frequent_earliest: for value in nums:
nums=[2, 1, 2, 1]; counts={2:2, 1:2}; value=1; best=2

Result: 2. Two and one tie; two appeared first.

most_frequent_earliest([])

L2 most_frequent_earliest: if not nums:
nums=[]

Result: None. No candidate exists.

Why the solution is correct

After counting, all comparisons use final rather than provisional frequencies. Strict replacement picks a larger frequency but never displaces an earlier equal-frequency value. The scan thus optimizes frequency first and occurrence order second.

Time and space

O(n) expected time and O(u) space.

Common mistakes

Using >= lets a later tied value win. A one-pass leader updated only on larger current counts does not automatically implement final-frequency earliest ties.

Reasoning card

State: counts contains final frequencies. best is the earliest encountered value among those with the largest frequency examined so far.

Invariant: The chosen candidate obeys both frequency and tie rules.

Decision to rehearse: Coordinate frequency and first-position state.

Finish: Return best

Transfer exercise

Break ties by the smallest value instead; express the two-part ordering explicitly.