LeetCode 1560 - Most Visited Sector in a Circular Track

In this problem, we are given a circular track divided into n sectors, numbered from 1 to n. A marathon runner moves around this track in increasing numerical order, and after sector n, the runner wraps back to sector 1.

leetcodeeasyarraysimulation

LeetCode Problem 1560

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

In this problem, we are given a circular track divided into n sectors, numbered from 1 to n. A marathon runner moves around this track in increasing numerical order, and after sector n, the runner wraps back to sector 1.

The input array rounds describes the sequence of rounds in the marathon. Each consecutive pair of values represents a path traveled by the runner:

  • The runner starts at rounds[i - 1]
  • The runner finishes at rounds[i]

While moving, every sector passed through is considered visited, including the ending sector of each round.

The task is to determine which sectors are visited the maximum number of times during the entire marathon. The result must be returned in ascending order.

The constraints are very small:

  • 2 <= n <= 100
  • 1 <= m <= 100

This means even a direct simulation approach is feasible because the total number of sectors traversed is limited. However, the problem contains a very important observation that allows us to solve it even more elegantly.

One subtle aspect of the problem is how visits are counted. The runner continuously moves forward in circular order, so a transition from sector 4 to sector 1 on a track of size 4 means the runner passes through sector 4 and then wraps to 1.

Several edge cases are important:

  • The path may wrap around the circular boundary multiple times.
  • The start sector and end sector may produce a range that crosses n.
  • Every sector may become equally visited.
  • The answer may contain only one sector.
  • Since the marathon is continuous, naive counting implementations can accidentally double count sectors at round boundaries.

The problem guarantees that consecutive values in rounds are different, so every round involves actual movement.

Approaches

Brute Force Simulation

The most straightforward solution is to simulate the entire marathon exactly as described.

We maintain a frequency array where count[i] stores how many times sector i has been visited. Starting from rounds[0], we simulate every step around the circular track until reaching the next destination sector.

For each movement:

  • Increment the visit count of the current sector
  • Move to the next sector
  • Wrap from n back to 1 when necessary

After processing all rounds, we find the maximum frequency and return all sectors that match it.

This approach is correct because it literally follows the movement rules given in the statement. However, it performs unnecessary work because the problem has a hidden mathematical structure.

Key Insight for the Optimal Solution

The important observation is that the most visited sectors are always the sectors encountered between the starting sector of the marathon and the final ending sector, moving in increasing circular order.

Why does this happen?

During every complete lap around the track, every sector is visited exactly once. Therefore, complete cycles contribute equally to all sectors and do not affect which sectors are most visited.

The only sectors that receive one additional visit are the sectors traversed in the final partial segment, from:

  • rounds[0] to rounds[-1]

If the start sector is less than or equal to the end sector, the answer is simply:

[start, start + 1, ..., end]

Otherwise, the path wraps around:

[start, ..., n, 1, ..., end]

This gives a very compact and elegant solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(total traversed sectors) O(n) Simulates every movement explicitly
Optimal O(n) O(1) excluding output Uses the circular traversal observation

Algorithm Walkthrough

Optimal Algorithm

  1. Identify the starting sector and ending sector.

The marathon begins at rounds[0] and finishes at rounds[-1]. These two values determine the sectors that receive the extra visit count. 2. Check whether the traversal wraps around the circular boundary.

If start <= end, the path is a normal increasing range without wrapping.

If start > end, the traversal crosses sector n and continues again from sector 1. 3. Construct the answer for the non-wrapping case.

When start <= end, every sector in the interval:

start to end

receives the maximum number of visits. 4. Construct the answer for the wrapping case.

When wrapping occurs, the most visited sectors are:

start to n
followed by
1 to end
  1. Return the sectors in ascending order.

The required output format already matches the order produced by the construction above.

Why it works

Every complete revolution around the track contributes exactly one visit to every sector, so all sectors receive the same baseline number of visits.

The only difference comes from the incomplete portion of the marathon, which starts at rounds[0] and ends at rounds[-1]. Those sectors receive one additional visit, making them the most visited sectors overall.

Python Solution

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))

        return list(range(start, n + 1)) + list(range(1, end + 1))

The implementation first extracts the starting and ending sectors.

If the start sector is less than or equal to the end sector, the answer is simply the continuous range between them.

Otherwise, the traversal wraps around the circular boundary. In that case, we combine two ranges:

  • start through n
  • 1 through end

The code directly mirrors the mathematical observation from the algorithm discussion, which keeps the implementation extremely concise.

Go Solution

func mostVisited(n int, rounds []int) []int {
    start := rounds[0]
    end := rounds[len(rounds)-1]

    result := []int{}

    if start <= end {
        for i := start; i <= end; i++ {
            result = append(result, i)
        }
        return result
    }

    for i := start; i <= n; i++ {
        result = append(result, i)
    }

    for i := 1; i <= end; i++ {
        result = append(result, i)
    }

    return result
}

The Go implementation follows the same logic as the Python version.

Since Go does not have a built in equivalent of Python's range, we manually append values into the result slice using loops.

There are no concerns about integer overflow because the constraints are extremely small. The solution uses slices dynamically, which naturally handles the variable output size.

Worked Examples

Example 1

Input:
n = 4
rounds = [1,3,1,2]

The marathon starts at sector 1 and ends at sector 2.

Since 1 <= 2, there is no wraparound in the final traversal interval.

The most visited sectors are:

[1, 2]

Actual traversal:

Step Sector Visited
Start 1
Move 2
Move 3
Move 4
Move 1
Move 2

Visit counts:

Sector Visits
1 2
2 2
3 1
4 1

Result:

[1, 2]

Example 2

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

Start sector:

2

End sector:

2

Since start <= end, the answer is simply:

[2]

Visit frequencies confirm that sector 2 is visited more often than sector 1.

Example 3

Input:
n = 7
rounds = [1,3,5,7]

Start sector:

1

End sector:

7

Since 1 <= 7, all sectors between them are included.

Result:

[1,2,3,4,5,6,7]

Every sector receives the same number of visits.

Complexity Analysis

Measure Complexity Explanation
Time O(n) At most all sectors are added once to the answer
Space O(1) excluding output Only a few variables are used

The algorithm only constructs the final answer array. Since the answer itself may contain up to n sectors, the runtime is linear in the number of sectors included.

No auxiliary data structures such as hash maps or frequency arrays are needed.

Test Cases

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))

        return list(range(start, n + 1)) + list(range(1, end + 1))

sol = Solution()

assert sol.mostVisited(4, [1,3,1,2]) == [1,2]  # provided example with wraparound
assert sol.mostVisited(2, [2,1,2,1,2,1,2,1,2]) == [2]  # repeated oscillation
assert sol.mostVisited(7, [1,3,5,7]) == [1,2,3,4,5,6,7]  # all sectors equally visited

assert sol.mostVisited(5, [2,3]) == [2,3]  # simple non-wrapping path
assert sol.mostVisited(5, [4,2]) == [1,2,4,5]  # wrapping path
assert sol.mostVisited(3, [1,2,3,1]) == [1]  # full cycle ending at start
assert sol.mostVisited(6, [6,1]) == [1,6]  # direct wraparound
assert sol.mostVisited(8, [5,6,7,8]) == [5,6,7,8]  # increasing traversal
assert sol.mostVisited(8, [7,2]) == [1,2,7,8]  # wraparound with multiple sectors

Test Summary

Test Why
n=4, [1,3,1,2] Verifies standard wraparound behavior
n=2, [2,1,2,1,2...] Tests repeated cycling between two sectors
n=7, [1,3,5,7] Validates case where all sectors are most visited
n=5, [2,3] Small non-wrapping interval
n=5, [4,2] Confirms circular wrapping logic
n=3, [1,2,3,1] Tests ending at the start sector
n=6, [6,1] Minimal wraparound case
n=8, [5,6,7,8] Straight increasing traversal
n=8, [7,2] Larger wraparound interval

Edge Cases

One important edge case occurs when the path wraps around the circular boundary. For example, if the traversal starts at sector 5 and ends at sector 2, a naive implementation may incorrectly assume the range is empty because 5 > 2. The correct interpretation is that the runner moves from 5 to n, then continues from 1 to 2. The implementation handles this by splitting the answer construction into two ranges.

Another important case occurs when every sector becomes equally visited. This happens when the start sector is 1 and the final sector is n. In that situation, every sector lies inside the final traversal interval, so the answer includes all sectors. The implementation naturally handles this with the standard non-wrapping range construction.

A third edge case is when the answer contains only one sector. For example, repeated oscillation between two sectors may make only one sector receive the extra visit count. The implementation correctly returns a single-element array because the range construction still works even when start == end.

Finally, very small values of n, such as n = 2, can expose off-by-one bugs in circular traversal logic. Since the solution relies purely on interval construction rather than manual simulation, it avoids many common boundary mistakes.