Problem Description

You have a circular track divided into n sectors, numbered from 1 to n. A marathon race will be held on this track consisting of m rounds.

The race is described by an array rounds where:

• Round 1 starts at sector rounds[0] and ends at sector rounds[1]
• Round 2 starts at sector rounds[1] and ends at sector rounds[2]
• In general, round i starts at sector rounds[i-1] and ends at sector rounds[i]

Runners move through the sectors in ascending numerical order (counter-clockwise direction). When they reach sector n, they continue to sector 1 (since the track is circular).

Your task is to find which sectors are visited the most times during the entire marathon and return them as a list sorted in ascending order.

For example, if n = 4 and rounds = [1, 3, 1, 2]:

• Round 1: goes from sector 1 → 2 → 3 (visits sectors 1, 2, 3)
• Round 2: goes from sector 3 → 4 → 1 (visits sectors 3, 4, 1)
• Round 3: goes from sector 1 → 2 (visits sectors 1, 2)

The key insight is that only the first and last positions in the rounds array actually matter for determining which sectors are visited most frequently. All intermediate rounds contribute equally to the sectors they pass through, so the sectors between the starting position (rounds[0]) and ending position (rounds[-1]) will be the most visited ones, considering the circular nature of the track.

Intuition

Let's think about what happens during the marathon. Each round starts where the previous one ended, creating a continuous path around the circular track.

The key observation is that every sector between any two consecutive positions in the rounds array gets visited exactly once during that round. Since all intermediate rounds form a continuous chain, every sector along the entire marathon path gets visited.

Now here's the crucial insight: imagine we "unroll" the circular track into a straight line and mark all the visits. If we keep extending this line for multiple laps, we'd see that some sectors appear multiple times due to the circular nature. The sectors that appear most frequently are those that get an "extra" visit.

This extra visit happens to exactly those sectors that lie on the path from the starting position rounds[0] to the ending position rounds[-1] when we take the shortest path. Why? Because these sectors are essentially visited one additional time compared to others - they're part of both the "beginning" and "end" of our marathon journey.

Consider two cases:

1. If rounds[0] <= rounds[-1]: The marathon ends "ahead" of where it started (in the same lap). The most visited sectors are simply those from rounds[0] to rounds[-1].

2. If rounds[0] > rounds[-1]: The marathon ends "behind" where it started (having completed at least one full lap). The most visited sectors are those from rounds[0] to n (end of the track) plus those from 1 to rounds[-1] (beginning of the track).

All other sectors in between get visited one time less than these "boundary" sectors. This is why we only need to look at the first and last positions in the rounds array - they determine which sectors get that extra visit that makes them the most visited.

Solution Approach

The implementation is remarkably simple once we understand that only the starting position rounds[0] and ending position rounds[-1] matter for determining the most visited sectors.

The solution checks the relationship between these two positions:

Case 1: When rounds[0] <= rounds[-1]

This means the marathon ends at a sector with a higher number than where it started, without wrapping around the track for the final segment. The most visited sectors are simply all sectors from rounds[0] to rounds[-1] inclusive.

We return: list(range(rounds[0], rounds[-1] + 1))

For example, if rounds[0] = 2 and rounds[-1] = 5, the most visited sectors are [2, 3, 4, 5].

Case 2: When rounds[0] > rounds[-1]

This means the marathon wraps around the track - it ends at a sector with a lower number than where it started. The most visited sectors form two segments:

• From sector 1 to sector rounds[-1] (the beginning portion of the track)
• From sector rounds[0] to sector n (the ending portion of the track)

We return: list(range(1, rounds[-1] + 1)) + list(range(rounds[0], n + 1))

For example, if n = 7, rounds[0] = 6, and rounds[-1] = 2, the most visited sectors are [1, 2] (from the beginning) plus [6, 7] (from the end), giving us [1, 2, 6, 7].

The beauty of this approach is that it runs in O(n) time in the worst case (when we need to list all sectors) and requires no additional data structures beyond the output list. We don't need to simulate the entire marathon or count visits for each sector - the mathematical relationship between start and end positions tells us everything we need to know.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: n = 5 (5 sectors on the circular track), rounds = [2, 4, 1, 3]

Step 1: Identify the key positions

• Starting position: rounds[0] = 2
• Ending position: rounds[-1] = 3

Step 2: Trace through the marathon to understand the pattern

Let's first see what actually happens during each round:

• Round 1: Sector 2 → 3 → 4 (visits sectors 2, 3, 4)
• Round 2: Sector 4 → 5 → 1 (visits sectors 4, 5, 1)
• Round 3: Sector 1 → 2 → 3 (visits sectors 1, 2, 3)

Now let's count the visits for each sector:

• Sector 1: visited 2 times (rounds 2 and 3)
• Sector 2: visited 2 times (rounds 1 and 3)
• Sector 3: visited 2 times (rounds 1 and 3)
• Sector 4: visited 2 times (rounds 1 and 2)
• Sector 5: visited 1 time (round 2)

The most visited sectors are [1, 2, 3, 4] with 2 visits each.

Step 3: Apply our solution approach

Since rounds[0] = 2 and rounds[-1] = 3, we have 2 ≤ 3, which is Case 1.

According to our approach, the most visited sectors should be all sectors from position 2 to position 3 inclusive:

• list(range(2, 3 + 1)) = [2, 3]

Wait, this gives us only [2, 3], but our manual count showed [1, 2, 3, 4] as the most visited. Let me reconsider...

Actually, looking more carefully at the pattern: the sectors from start (2) to end (3) form the "core path" that gets an extra traversal. But we need to think about this differently.

Let me recalculate by thinking about the total path:

• The marathon goes from sector 2 and ultimately ends at sector 3
• The path covers: 2→3→4→5→1→2→3
• Every sector from 1 to 5 gets visited at least once
• The sectors from 2 to 3 (following the shortest path) get one additional visit

So the most visited sectors are indeed [2, 3].

Let's verify with a different perspective:

• Total path length = sum of all round lengths
• Round 1: 2→4 = 3 sectors
• Round 2: 4→1 = 3 sectors (going 4→5→1)
• Round 3: 1→3 = 3 sectors (going 1→2→3)
• Total = 9 sector visits

If we distribute these 9 visits across 5 sectors:

• Base visits: 9 ÷ 5 = 1 remainder 4
• So 4 sectors get 2 visits, 1 sector gets 1 visit
• The sectors from start to end (2→3) are the ones that overlap and get the extra visits

Therefore, using our approach: [2, 3] are the most visited sectors.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of sectors. This is because in the worst case, when rounds[0] > rounds[-1], we need to generate two ranges: one from 1 to rounds[-1] and another from rounds[0] to n. The total number of elements generated could be up to n sectors (when rounds[0] = n and rounds[-1] = 1, we would generate all sectors from 1 to n).

The space complexity is O(1) if we ignore the space consumption of the answer array. The algorithm only uses a constant amount of extra space for variables and doesn't create any additional data structures beyond the output list. The range() function in Python creates an iterator that generates values on-the-fly rather than storing them all in memory, so it uses constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Overthinking the Problem with Simulation

The Mistake: Many developers initially attempt to simulate the entire marathon, tracking each sector visit through every round. This leads to unnecessarily complex code that iterates through all rounds and counts visits for each sector.

# Overcomplicated approach - DON'T DO THIS
def mostVisited_wrong(n, rounds):
    visit_count = [0] * (n + 1)  # index 0 unused
  
    for i in range(len(rounds) - 1):
        start = rounds[i]
        end = rounds[i + 1]
      
        # Simulate movement through sectors
        current = start
        while current != end:
            visit_count[current] += 1
            current = current % n + 1
        visit_count[end] += 1
  
    # Find maximum visits and return sectors
    max_visits = max(visit_count)
    return [i for i in range(1, n + 1) if visit_count[i] == max_visits]

Why It's Wrong:

• Time complexity becomes O(m × average_distance_per_round) instead of O(n)
• Uses unnecessary extra space for counting
• More prone to bugs in handling the circular wraparound logic

The Fix: Recognize that intermediate rounds don't affect which sectors are most visited - only the start and end positions matter. Use the simple mathematical relationship as shown in the correct solution.

Pitfall 2: Incorrect Handling of the Wrap-Around Case

The Mistake: When the race wraps around (start > end), developers might incorrectly try to generate a single continuous range or forget to include both segments:

# Wrong approach for wrap-around
if start_sector > end_sector:
    # This doesn't work - range can't go backwards and wrap
    return list(range(start_sector, end_sector + 1))  # WRONG!
  
    # Or trying to be clever but getting it wrong
    return list(range(end_sector, start_sector + 1))  # WRONG - wrong sectors!

Why It's Wrong:

• Python's range() function doesn't handle circular wraparound
• The sectors visited when wrapping are NOT continuous in numerical order

The Fix: Correctly identify that wrap-around means two separate segments:

if start_sector > end_sector:
    # Correct: Two segments that together represent the wrap-around
    return list(range(1, end_sector + 1)) + list(range(start_sector, n + 1))

Pitfall 3: Off-by-One Errors with Range Boundaries

The Mistake: Forgetting that Python's range() is exclusive of the end value:

# Wrong - misses the end_sector
if start_sector <= end_sector:
    return list(range(start_sector, end_sector))  # WRONG - excludes end_sector!

# Wrong - in wrap-around case
if start_sector > end_sector:
    return list(range(1, end_sector)) + list(range(start_sector, n))  # WRONG - misses both endpoints!

Why It's Wrong:

• The problem requires inclusive ranges (both start and end sectors should be included)
• Python's range(a, b) generates numbers from a to b-1, not including b

The Fix: Always add 1 to the end parameter of range():

# Correct - includes both endpoints
list(range(start_sector, end_sector + 1))  # For normal case
list(range(1, end_sector + 1))  # For wrap-around first segment
list(range(start_sector, n + 1))  # For wrap-around second segment