Most visited position on a track

A track has positions numbered 1 to n. A runner does a series of sprints: sprints[0] is where the first sprint starts, and each sprint runs from sprints[i] to sprints[i + 1], in whichever direction gets there directly. A sprint visits every position from its start to its end, both inclusive. Return the position visited most often; if several tie, return the smallest.

A position where one sprint ends and the next one starts is counted once for each of those two sprints.

Interface

Unless you agree on a different interface with the interviewer, assume:

• most_visited(n: int, sprints: list[int]) -> int — the smallest position with the highest visit count.

Example

most_visited(5, [2, 4, 1, 3])  ->  2
# 2 -> 4 visits 2, 3, 4;  4 -> 1 visits 4, 3, 2, 1;  1 -> 3 visits 1, 2, 3
# counts: 1:2  2:3  3:3  4:2  5:0   -> positions 2 and 3 tie, return 2

most_visited(4, [1, 4])        ->  1    # every position visited once

Constraints

• 1 <= n <= 10^5; 2 <= len(sprints) <= 10^5; every entry is in [1, n].
• Consecutive entries are different.

Clarifying questions

• Does a sprint ever wrap around past position n back to 1, or does it always go directly?
• Is the shared endpoint of two consecutive sprints counted once or twice?
• On a tie, smallest position or all of them?

What a strong answer covers

• The naive way adds 1 to every position of every sprint: O(n · m) in the worst case.
• A difference array: for each sprint, +1 at its lower end and -1 just past its upper end, then one prefix-sum pass and a scan for the maximum. O(n + m) time, O(n) space.
• Getting the inclusive bounds and the shared endpoints right.
• Tests: two sprints, sprints going back and forth, n = 1-style tiny cases, a position never visited.

Follow-ups

• The track is a loop and each sprint goes forward only, wrapping from n to 1. Adjust the difference array.
• Return every most-visited position.
• n is up to 10^9 but there are few sprints. Use coordinate compression.