Katkat
Back

Find the Most Visited Track Position

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Determine the most frequently visited track position given a series of sprint endpoints by efficiently tallying overlapping intervals.

Problem Statement

A runner is training on a linear track with positions numbered consecutively from 1 to n. The training session consists of moving between checkpoints specified by an array sprints of length m.

For each consecutive pair of checkpoints (sprints[i], sprints[i + 1]) for 0 <= i < m - 1, the runner traverses every position between sprints[i] and sprints[i + 1], inclusive. Note that the runner can move in either direction (left-to-right or right-to-left).

Find the position that is visited the greatest number of times across the entire training session. If there are multiple positions tied for the maximum number of visits, return the one with the smallest position number.

Function Signature

def most_visited_position(n: int, sprints: list[int]) -> int:
    pass

Constraints

  • 2 <= n <= 10^5
  • 2 <= len(sprints) <= 10^5
  • 1 visits [2, 3, 4]`
  • Segment 2: from 4 to 1 -> visits [1, 2, 3, 4]
  • Segment 3: from 1 to 3 -> visits [1, 2, 3]

Total visit counts:

  • Position 1: 2 visits
  • Position 2: 3 visits
  • Position 3: 3 visits
  • Position 4: 2 visits
  • Position 5: 0 visits

The maximum visits is 3, achieved at positions 2 and 3. The smallest index among them is 2.

Example 2

Input: n = 4, sprints = [1, 4]
Output: 1

Explanation: The runner visits positions 1, 2, 3, and 4 once each. All positions are tied with 1 visit, so the smallest position 1 is returned.

Edge Cases to Consider

  • Consecutive endpoints that are identical (sprints[i] == sprints[i + 1]), where only a single position is visited.
  • Unvisited positions on the track.
  • A runner covering the entire track multiple times back and forth.

Hints

Hint 1

A brute-force increment for every step in each sprint leg takes O(m * n) time, which will be too slow for the upper constraints.

Hint 2

Notice that each leg simply increments a contiguous range [min(a, b), max(a, b)] by 1.

Hint 3

Use a difference array to record range increments in O(1) time per sprint, then compute prefix sums to evaluate total visits in O(n) time.

Follow-up questions

  • How would you solve the problem if n can be up to 10^9 while m remains at most 10^5?
  • How would your approach adapt if each sprint interval had an associated floating-point score/weight rather than a visit count of 1?
  • If sprints were added dynamically in an online stream and we frequently needed to query the most visited position, what data structure would you use?