Find the Most Visited Track Position
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```text
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
```text
n = 5
sprints = [4, 2]
Output: 2
```
Positions 2, 3, and 4 each receive one visit. Position 2 wins the tie.
Overview: Count visits along inclusive sprint intervals in either direction and return the smallest numbered position among those visited most often.
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
```text
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
```text
n = 5
sprints = [4, 2]
Output: 2
```
Positions 2, 3, and 4 each receive one visit. Position 2 wins the tie.
Constraints
- 1 <= n <= 1000000.
- 1 <= sprints.length <= 100000; every sprint position lies between 1 and n.
- Each adjacent pair visits both endpoints and every position between them once, in either direction.
- Shared endpoints count separately for each leg; a stationary leg counts once.
- Return the smallest most-visited position; with no legs, return 1.
Examples
Input: (5, [1, 3, 5])
Expected Output: 3
Explanation: Published sample 1: the shared endpoint 3 receives two visits.
Input: (5, [4, 2])
Expected Output: 2
Explanation: Published sample 2: the inclusive interval 2 through 4 ties, so return 2.