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).
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 <= 1001 <= m <= 100rounds.length == m + 11 <= rounds[i] <= nrounds[i] != rounds[i + 1] for 0 <= i < mProblem Overview: You have n sectors arranged in a circular track labeled from 1 to n. A runner completes several rounds defined by the rounds array. Each element marks the sector where a round starts and the next element marks where it ends. The task is to determine which sectors are visited the most during the entire run.
Approach 1: Direct Traversal Using Modulo (Simulation) (Time: O(k), Space: O(n))
This approach simulates the runner's movement step by step. Start at rounds[0], then repeatedly move to the next sector using modulo arithmetic: sector = (sector % n) + 1. Maintain a frequency array to count how many times each sector is visited. For every segment from rounds[i] to rounds[i+1], iterate forward across the circular track and update counts. After processing all rounds, scan the frequency array to find sectors with the maximum visit count.
This method is straightforward and mirrors the real movement on the track. It works well when constraints are small and you want a clear simulation of the process. However, it performs unnecessary work because many visits follow a predictable pattern.
Approach 2: Efficient Range Computation (Time: O(n), Space: O(1) excluding output)
The key observation: the most visited sectors are simply the sectors encountered in the final stretch from the first round's start to the last round's end. Earlier rounds add equal counts to intermediate sectors, so they do not affect which sectors end up with the maximum frequency.
If rounds[0] <= rounds[m-1], the most visited sectors are the continuous range [rounds[0], rounds[m-1]]. If the path wraps around the circle (rounds[0] > rounds[m-1]), the answer becomes two ranges: [1, rounds[m-1]] and [rounds[0], n]. Construct the result in ascending order as required by the problem.
This works because the runner repeatedly passes through sectors in the same direction. The sectors between the first and last positions receive one additional visit compared to others. The solution relies on simple array traversal rather than full simulation, making it both cleaner and faster.
Recommended for interviews: The efficient range computation approach is what interviewers expect. It shows you identified the repeating traversal pattern instead of brute‑forcing the simulation. Walking through the simulation approach first can demonstrate understanding, but deriving the range insight proves stronger algorithmic reasoning.
This approach involves simulating the path of the marathon directly by iterating from the start of each round to the end sector. We make use of the circular nature of the track by employing modulus calculations to wrap around the path when it exceeds the number of sectors, ensuring that the path remains continuous. We keep a count of visits for each sector and determine the maximum visit count. Then, we compile all sectors with this maximum visit count into our result.
We first initialize an array to count the visits per sector, then loop through the rounds. For each round, iterate from start to end, updating the visit count and wrapping around using modulo. Finally, collect and return the sectors with the maximum visit counts.
Time Complexity: O(m * n), where m is roundsSize. Space Complexity: O(n) for the visit count array.
An alternative solution that leverages the nature of a circular array. This approach focuses directly on the last start and end since it implies the maximal presence of sectors. This problem is simplified using direct range calculation based on the first and last elements of rounds. Specifically, if starting is less than or equal to the end, then the sectors between the start and end are the most visited. If the start is greater than end (indicating wrap-around), then sectors from 1 to end and from start to n are the most visited.
This C solution makes use of direct iteration over a set range. Memory allocation is dynamic, with sectors directly appended according to calculated ranges.
Time Complexity: O(n) in worst-case scenario. Space Complexity: O(1) for the result as it is determined by fixed parameters.
Since the end position of each stage is the start position of the next stage, and each stage is in a counterclockwise direction, we can determine the number of times each sector is passed based on the relationship between the start and end positions.
If rounds[0] leq rounds[m], then the sectors from rounds[0] to rounds[m] are passed the most times, and we can directly return all sectors within this interval.
Otherwise, the sectors from 1 to rounds[m] and the sectors from rounds[0] to n form the union of the most passed sectors, and we can return the union of these two intervals.
The time complexity is O(n), where n is the number of sectors. Ignoring the space consumption of the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Traversal Using Modulo | Time Complexity: O(m * n), where m is roundsSize. Space Complexity: O(n) for the visit count array. |
| Efficient Range Computation | Time Complexity: O(n) in worst-case scenario. Space Complexity: O(1) for the result as it is determined by fixed parameters. |
| Considering the Relationship Between Start and End Positions | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Traversal Using Modulo (Simulation) | O(k) where k is total sector moves | O(n) | When you want a straightforward simulation of the runner's movement |
| Efficient Range Computation | O(n) | O(1) excluding output | Preferred solution when recognizing the circular traversal pattern |
1560. Most Visited Sector in a Circular Track (Leetcode Easy) • Programming Live with Larry • 2,056 views views
Watch 4 more video solutions →Practice Most Visited Sector in a Circular Track with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor