Find the Most Visited Track Position

A track has positions numbered from 1 through n. A runner follows the positions in sprints, moving from sprints[i] to sprints[i + 1] for every adjacent pair.

Each leg visits every numbered position between its endpoints, including both endpoints, once. Implement mostVisited(n, sprints) and return the smallest position number among those with the greatest total number of visits.

Rules and Constraints

• A leg may move in either direction.
• A shared endpoint belongs to both neighboring legs and receives one visit from each.
• A leg whose start and end are the same position visits that position once.
• With a single supplied position there are no legs and all visit counts are zero, so return 1.
• 1 <= n <= 1,000,000.
• 1 <= sprints.length <= 100,000, and every supplied position is from 1 through n.

Example 1

n = 5
sprints = [1, 3, 5]
Output: 3

The visit counts at positions 1 through 5 are [1, 1, 2, 1, 1]. Position 3 is counted in both legs.

Example 2

n = 5
sprints = [4, 2]
Output: 2

Positions 2, 3, and 4 each receive one visit. Position 2 wins the tie.

Find the Most Visited Track Position

Approach

Represent each leg as an inclusive interval [left, right], independent of movement direction. Add one to a difference array at left and subtract one immediately after right. A prefix sum across positions 1 through n then gives every total visit count.

An interval's increment remains active from left through right and is canceled at right + 1. Summing these independent contributions counts each leg once at exactly its visited positions. In particular, two neighboring legs both contribute at a shared endpoint, and a stationary leg activates the increment for its single position only.

Scan positions in increasing order and replace the answer only when a strictly larger visit count appears. After each position, the answer is the smallest position achieving the greatest count seen so far. This proves the final tie-breaking rule. With one supplied sprint position, there are no interval updates; every count is zero, so the increasing scan keeps position 1.

For m supplied positions, processing the legs takes O(m) time and scanning the track takes O(n) time. The difference array uses O(n) auxiliary space. No per-leg traversal of the full interval is needed, and each visit count is at most m - 1, within signed 32-bit range.

• Time complexity: O(n + m), where m = sprints.length.
• Space complexity: O(n) auxiliary space.