Taro Logo

Most Visited Sector in a Circular Track

#10 Most AskedEasy
Topics:
Arrays

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 <= 100
  • 1 <= m <= 100
  • rounds.length == m + 1
  • 1 <= rounds[i] <= n
  • rounds[i] != rounds[i + 1] for 0 <= i < m

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Are the sectors numbered from one through the size of the track?
  2. Does the runner move only toward higher numbers, wrapping from the last sector back to sector one?
  3. Is the opening sector counted before the runner takes the first step?
  4. Should every sector that ties for the most visits be returned in ascending order?
  5. Do extra complete laps change which sectors are strictly the most visited?

Brute Force Solution

Approach

The runner is placed on the opening sector and that visit is recorded. Each checkpoint is then reached by stepping forward one sector at a time, wrapping from the last sector back to sector one, and every sector entered along the way is counted. After the last checkpoint, the sectors whose counts equal the highest count are returned in ascending order.

Here's how the algorithm would work step-by-step:

  1. Create a counter for every sector and record one visit at the opening sector.
  2. Take each checkpoint in order as the end of the next stretch.
  3. Advance one sector at a time until that checkpoint is reached.
  4. Wrap back to sector one whenever a step would pass the last sector.
  5. Add one visit to every sector entered during those steps.
  6. Find the largest visit count on the track.
  7. Collect every sector that has that count, scanning from sector one upward.

Code Implementation

def mostVisited(number_of_sectors, rounds):
    visit_counts = [0] * (number_of_sectors + 1)
    
    current_position = rounds[0]
    visit_counts[current_position] += 1
    
    for destination_index in range(1, len(rounds)):
        start_position = rounds[destination_index - 1]
        end_position = rounds[destination_index]
        
        # This loop simulates the runner moving one sector at a time to the next checkpoint.
        current_sector_in_lap = start_position
        while current_sector_in_lap != end_position:
            current_sector_in_lap += 1
            
            # This check handles the circular nature of the track by wrapping around to sector 1.
            if current_sector_in_lap > number_of_sectors:
                current_sector_in_lap = 1
            
            visit_counts[current_sector_in_lap] += 1
            
    # After simulating the whole race, we need to find the highest visit count to identify the answer.
    maximum_visits = 0
    for sector_index in range(1, number_of_sectors + 1):
        if visit_counts[sector_index] > maximum_visits:
            maximum_visits = visit_counts[sector_index]
    
    most_visited_sectors = []
    for sector_index in range(1, number_of_sectors + 1):
        if visit_counts[sector_index] == maximum_visits:
            most_visited_sectors.append(sector_index)
            
    return most_visited_sectors

Big(O) Analysis

Time Complexity
O(n * m) – Let n be the number of sectors and let m be the number of stretches between consecutive checkpoints. Each stretch moves forward and can pass every sector at most once before it reaches its checkpoint, so one stretch costs O(n) steps. Repeating that walk for every stretch costs O(n * m) steps. Finding the maximum and collecting the winning sectors each scan the n counters once. Those final scans are absorbed by the same bound, so the total time is O(n * m).
Space Complexity
O(n) – A counter is stored for every sector, including an unused slot so sector numbers can be used directly. The answer list holds at most one entry per sector. The walk reuses a single current sector and does not keep the path. The checkpoint list is the input. The extra memory is O(n).

Optimal Solution

Approach

Every complete lap visits all sectors the same number of times, so those laps cannot change which sectors are strictly ahead. Only the forward arc from the opening sector to the final checkpoint can be ahead, wrapping past the last sector when the finish number is smaller. That arc is collected and then sorted.

Here's how the algorithm would work step-by-step:

  1. Read the opening sector and the final checkpoint.
  2. Ignore the intermediate checkpoints, because full laps visit every sector equally.
  3. When the finish number is at least the start number, collect every sector from the start through the finish.
  4. When the finish number is smaller, collect sectors one through the finish.
  5. Also collect sectors from the start through the last sector in that wrapping case.
  6. Sort the collected sectors into ascending order.
  7. Return that sorted list as the most visited sectors.

Code Implementation

def mostVisited(number_of_sectors, rounds_array):
    start_sector = rounds_array[0]
    end_sector = rounds_array[-1]
    
    most_visited_sectors = []

    # The core insight is that full laps can be ignored, as they visit every sector equally.
    # We only need to consider the path of the final partial lap from the start to the end sector.
    if start_sector <= end_sector:
        # If the race ends at or after the start sector, the path is a simple forward traversal.
        for sector in range(start_sector, end_sector + 1):
            most_visited_sectors.append(sector)
    else:
        # If the end is before the start, the path crosses the circular track's boundary.
        # This means the path covers from start to 'n' and then from 1 to the end.
        for sector in range(1, end_sector + 1):
            most_visited_sectors.append(sector)
        for sector in range(start_sector, number_of_sectors + 1):
            most_visited_sectors.append(sector)
            
    return sorted(most_visited_sectors)

Big(O) Analysis

Time Complexity
O(n log n) – The intermediate checkpoints are never walked, so their count does not appear in the bound. Building the arc writes each chosen sector once, and there are at most n sectors. Sorting those sectors compares them a logarithmic number of times relative to how many were written. The two branches of the arc do a constant amount of bookkeeping besides those writes. The total time is O(n log n).
Space Complexity
O(n) – The result list stores at most every sector on the track. Sorting may use a small amount of additional working space proportional to that list. No visit counters are allocated. The checkpoint array is only read at its ends. The extra memory is O(n).

Edge Cases

The marathon finishes on the same sector number where it began
How to Handle:
The sectors from that opening number through the finish are the most visited ones.
The finish lies before the start on the numbered track
How to Handle:
The most visited sectors are those from one through the finish together with those from the start through the last sector.
Two sectors share the highest visit count
How to Handle:
Both sectors are returned, ordered from the smaller number to the larger number.
The track has only two sectors
How to Handle:
Movement still wraps between those two sectors, and the counts follow each forward step.
One round passes every sector
How to Handle:
Each sector is visited once, so the result lists every sector from one through the track size.
The opening sector is recorded before any movement
How to Handle:
That initial visit is included, so the opening sector can belong to the winning set.
0/54 completed