Problem

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Examples

Example 1

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2020/08/14/tmp.jpg)

Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.

Example 2

1
2

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]

Example 3

1
2

Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]

Constraints

  • 2 <= n <= 100
  • 1 <= m <= 100
  • rounds.length == m + 1
  • 1 <= rounds[i] <= n
  • rounds[i] != rounds[i + 1] for 0 <= i < m

Solution

Method 1 - Simulation

Intuition

Since the marathon always moves in ascending order (counter-clockwise), the most visited sectors are those between the starting sector and the ending sector of the last round, inclusive. We can simulate the path or use modular arithmetic to find the sectors visited most often.

Approach

The marathon starts at rounds[0] and ends at rounds[-1]. The sectors most visited are those from rounds[0] to rounds[-1] (inclusive), wrapping around if needed. We can construct the answer by iterating from start to end, handling the circular nature.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
    public List<Integer> mostVisited(int n, int[] rounds) {
        List<Integer> res = new ArrayList<>();
        int start = rounds[0], end = rounds[rounds.length - 1];
        if (start <= end) {
            for (int i = start; i <= end; i++) res.add(i);
        } else {
            for (int i = 1; i <= end; i++) res.add(i);
            for (int i = start; i <= n; i++) res.add(i);
        }
        return res;
    }
}
1
2
3
4
5
6

def mostVisited(n, rounds):
    start, end = rounds[0], rounds[-1]
    if start <= end:
        return list(range(start, end + 1))
    else:
        return list(range(1, end + 1)) + list(range(start, n + 1))

Complexity

  • ⏰ Time complexity: O(n) — We may visit all sectors once.
  • 🧺 Space complexity: O(n) — For the result list.