Module 01 · Execution Grammar and State Mutation

003. Maximum Value and First Index

Foundation · Download this solution · All solutions and shared helpers

Problem

Return (maximum_value, first_index) for a list of integers. Indices are zero-based. If the list is empty, return None. Equal later maxima must not replace the index of the first occurrence. Leave the input unchanged.

Examples

Example 1

maximum_first([4, 9, 2, 9])
=> (9, 1)

The second 9 does not win the tie.

Example 2

maximum_first([])
=> None

No maximum exists.

Example 3

maximum_first([-5, -1, -1])
=> (-1, 1)

The rule also works with negative maxima.

Reveal the worked solution and reasoning

Why this mechanism works

A scan needs only the best value seen and its position. The tie rule is part of correctness, not cosmetic output formatting. A strict improvement replaces the candidate; equality provides no reason to discard an earlier valid index. This distinction will reappear in stable ranking and shortest-path tie policies.

State and boundaries

best_value is the prefix maximum. best_index is its earliest position in that prefix.

Protocol

Handle empty input.
Seed the candidate from the first element.
Compare each later value to best_value.
Replace both fields only on a strictly larger value.
Return the pair.

Visualization

value:      4   9   2   9
best index: 0   1   1   1
                         equal: retain 1

Python implementation

def maximum_first(nums):
    if not nums:
        return None
    best_value, best_index = nums[0], 0
    for i in range(1, len(nums)):
        if nums[i] > best_value:
            best_value, best_index = nums[i], i
    return best_value, best_index

Worked execution

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

maximum_first([4, 9, 2, 9])

L2 maximum_first: if not nums:
nums=[4, 9, 2, 9]

L4 maximum_first: best_value, best_index = nums[0], 0
nums=[4, 9, 2, 9]; best_value=4; best_index=0

L5 maximum_first: for i in range(1, len(nums)):
nums=[4, 9, 2, 9]; best_value=4; best_index=0; i=1

L7 maximum_first: best_value, best_index = nums[i], i
nums=[4, 9, 2, 9]; best_value=9; best_index=1; i=1

L5 maximum_first: for i in range(1, len(nums)):
nums=[4, 9, 2, 9]; best_value=9; best_index=1; i=2

L5 maximum_first: for i in range(1, len(nums)):
nums=[4, 9, 2, 9]; best_value=9; best_index=1; i=3

Result: (9, 1). The second 9 does not win the tie.

maximum_first([])

L2 maximum_first: if not nums:
nums=[]

Result: None. No maximum exists.

Why the solution is correct

The seeded singleton satisfies both maximum and earliest-index requirements. A larger value invalidates the old maximum and becomes its first occurrence so far. Equal or smaller values leave the existing candidate valid. Thus the final pair meets both requirements.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Using >= returns the last maximum instead. Returning nums.index(max(nums)) works but hides the one-pass state mechanism being practiced.

Reasoning card

State: best_value is the prefix maximum. best_index is its earliest position in that prefix.

Invariant: best_index remains the first index of best_value.

Decision to rehearse: Use strict versus non-strict comparison deliberately.

Finish: Return the pair

Transfer exercise

Change the contract to the last occurrence and identify the single comparison that changes.