Difficulty: Easy | Acceptance: 59.90% | Paid: No Topics: Array, Simulation
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 i-th 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 (i.e., from sector 1 to sector n, then to sector 1, etc.).
- Examples
- Constraints
- Mathematical Approach
- Simulation Approach
Examples
Example 1
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
Input:
n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output:
[2]
Example 3
Input:
n = 7, rounds = [1,3,5,7]
Output:
[1,2,3,4,5,6,7]
Constraints
2 <= n <= 100
1 <= m == rounds.length <= 100
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] for all valid i
Mathematical Approach
Intuition The key observation is that the starting sector is visited at the beginning, and the ending sector is visited at the end. All sectors between them (in the direction of travel) are visited exactly once more than other sectors. Therefore, the most visited sectors form a contiguous range from start to end, wrapping around if necessary.
Steps
- Get the start sector (rounds[0]) and end sector (rounds[-1])
- If start <= end, return all sectors from start to end
- If start > end, return sectors from 1 to end, then from start to n
from typing import List
class Solution:
def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
start = rounds[0]
end = 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: O(n) for constructing the result array
- Space: O(n) for storing the result
- Notes: This is the optimal solution with constant time logic and linear space for output
Simulation Approach
Intuition Simulate the entire marathon by visiting each sector step by step, counting how many times each sector is visited. Then find all sectors with the maximum visit count.
Steps
- Initialize a count array of size n+1
- Start at rounds[0] and increment its count
- For each subsequent round, move sector by sector until reaching the target, incrementing counts
- Find the maximum count and return all sectors with that count
from typing import List
class Solution:
def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
count = [0] * (n + 1)
current = rounds[0]
count[current] += 1
for i in range(1, len(rounds)):
target = rounds[i]
while current != target:
current = current % n + 1
count[current] += 1
max_count = max(count)
return [i for i in range(1, n + 1) if count[i] == max_count]
Complexity
- Time: O(m × n) in worst case where m is rounds length
- Space: O(n) for the count array
- Notes: Less efficient than mathematical approach but more intuitive and easier to understand