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 < mWhen 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:
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:
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_sectorsEvery 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:
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)| Case | How to Handle |
|---|---|
| The marathon finishes on the same sector number where it began | The sectors from that opening number through the finish are the most visited ones. |
| The finish lies before the start on the numbered track | 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 | Both sectors are returned, ordered from the smaller number to the larger number. |
| The track has only two sectors | Movement still wraps between those two sectors, and the counts follow each forward step. |
| One round passes every sector | 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 | That initial visit is included, so the opening sector can belong to the winning set. |