Most Visited Sector in a Circular Track

Easy

#1436Time: O(m * n), where `m` is the number of rounds (`rounds.length - 1`) and `n` is the number of sectors. In the worst case, each of the `m` rounds can traverse all `n` sectors.Space: O(n) to store the visit counts for each sector in the `counts` array.1 company

Data structures

Array

Companies

Expedia

Prompt

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 i^th 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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the entire marathon as described in the problem. We maintain an array to store the visit count for each of the n sectors. We then traverse through all the rounds, and for each round, we simulate the path from the start sector to the end sector, incrementing the visit count for each sector along the path.

Algorithm

Initialize an integer array counts of size n + 1 to all zeros.
Increment the count for the starting sector of the marathon: counts[rounds[0]]++.
Iterate through the rounds array from i = 0 to rounds.length - 2.
Inside the loop, let start = rounds[i] and end = rounds[i+1].
Use a while loop to simulate the path from start to end. Let a current pointer start at start.
In each iteration of the while loop, move current to the next sector (circularly: (current == n) ? 1 : current + 1) and increment the count for this new sector in the counts array. Stop when current equals end.
After the outer loop finishes, find the maximum value, maxVisits, in the counts array.
Create a new list result.
Iterate from j = 1 to n. If counts[j] equals maxVisits, add j to result.
Return result.

Walkthrough

The core of this method is to keep a frequency map (an array counts of size n+1 works well for 1-based indexing) of the sectors. We start by noting the initial position of the marathon, rounds[0], and incrementing its count. Then, we loop through each of the m rounds defined by rounds[i] and rounds[i+1]. For each round, we simulate the movement from the current sector to the next, one step at a time, in a circular fashion. For every sector we land on, we increment its corresponding counter in our counts array. After simulating all the rounds, the counts array will hold the total number of visits for each sector. The final step is to find the maximum visit count and collect all sectors that have this count. Since the sectors need to be returned in ascending order, we can iterate from sector 1 to n to build the final result list.

1import java.util.ArrayList;2import java.util.List;3 4public class Solution {5    public List<Integer> mostVisited(int n, int[] rounds) {6        int[] counts = new int[n + 1];7        8        // The marathon starts at sector rounds[0].9        // We count this initial position.10        counts[rounds[0]]++;11        12        // Simulate each round13        for (int i = 0; i < rounds.length - 1; i++) {14            int start = rounds[i];15            int end = rounds[i+1];16            17            // Move from start to end, one sector at a time18            int current = start;19            while (current != end) {20                current = (current == n) ? 1 : current + 1;21                counts[current]++;22            }23        }24        25        // Find the maximum number of visits26        int maxVisits = 0;27        for (int count : counts) {28            if (count > maxVisits) {29                maxVisits = count;30            }31        }32        33        // Collect all sectors with the maximum number of visits34        List<Integer> result = new ArrayList<>();35        for (int i = 1; i <= n; i++) {36            if (counts[i] == maxVisits) {37                result.add(i);38            }39        }40        41        return result;42    }43}

Complexity

Time

O(m * n), where `m` is the number of rounds (`rounds.length - 1`) and `n` is the number of sectors. In the worst case, each of the `m` rounds can traverse all `n` sectors.

Space

O(n) to store the visit counts for each sector in the `counts` array.

Trade-offs

Pros

It's a straightforward implementation that directly models the process described in the problem.
Easy to understand and debug.

Cons

The time complexity is proportional to the total path length of the marathon, which can be large. It is inefficient if m or n are large, although it passes within the given constraints.

A more insightful approach recognizes that the intermediate stops in the marathon don't alter which sectors are visited most frequently. For any intermediate sector s = rounds[i] (where 0 < i < rounds.length - 1), the marathon arrives at s and then departs from s. These cancel each other out. Furthermore, any full laps of the track add one visit to every sector, so they don't change the relative ordering of visit counts. The only thing that creates a difference in visit counts is the path covered from the marathon's overall start point, rounds[0], to its overall end point, rounds[rounds.length - 1]. Therefore, the most visited sectors are simply those on this single, direct path.

Algorithm

Get the overall start sector, start = rounds[0], and the overall end sector, end = rounds[rounds.length - 1].
Create an empty list, result, to store the most visited sectors.
Check if start <= end:
- If true, the path is direct. Iterate from i = start to end and add each i to result.
Else (start > end):
- The path wraps around. To maintain sorted order in the result, first iterate from i = 1 to end and add each i to result.
- Then, iterate from i = start to n and add each i to result.
Return the result list.

Walkthrough

This optimized approach avoids simulating the entire marathon. The logic is based on a key observation: the relative frequency of visits is determined solely by the path from the first sector start = rounds[0] to the last sector end = rounds[rounds.length - 1]. Any full laps that occur during the intermediate rounds increase the visit count of every single sector by the same amount, thus not affecting which sectors are 'most' visited. The path segments between intermediate stops also have a net-zero effect on visit differentials. So, the problem reduces to finding all sectors on the path from start to end. There are two scenarios:

If start <= end, the path is a simple sequence: start, start + 1, ..., end.
If start > end, the path wraps around the circular track: start, start + 1, ..., n, 1, 2, ..., end. We can construct the list of these sectors directly. To ensure the output is sorted as required, if the path wraps around, we first add sectors from 1 to end and then from start to n.

1import java.util.ArrayList;2import java.util.List;3 4public class Solution {5    public List<Integer> mostVisited(int n, int[] rounds) {6        List<Integer> result = new ArrayList<>();7        int start = rounds[0];8        int end = rounds[rounds.length - 1];9        10        if (start <= end) {11            // Path does not wrap around12            for (int i = start; i <= end; i++) {13                result.add(i);14            }15        } else { // start > end16            // Path wraps around. Add segments to keep it sorted.17            // Segment 1: from 1 to end18            for (int i = 1; i <= end; i++) {19                result.add(i);20            }21            // Segment 2: from start to n22            for (int i = start; i <= n; i++) {23                result.add(i);24            }25        }26        27        return result;28    }29}

Complexity

Time

O(n). The time is dominated by the construction of the result list, which in the worst case involves iterating through all `n` sectors.

Space

O(n) for storing the result list. The size of the result can be up to `n`.

Trade-offs

Pros

Extremely efficient, as its runtime does not depend on the number of rounds m.
Simple to implement once the core insight is understood.

Cons

The logic is less intuitive and relies on an observation that might not be immediately obvious.

Solutions

Solution

1class Solution {2public3  List<Integer> mostVisited(int n, int[] rounds) {4    int m = rounds.length - 1;5    List<Integer> ans = new ArrayList<>();6    if (rounds[0] <= rounds[m]) {7      for (int i = rounds[0]; i <= rounds[m]; ++i) {8        ans.add(i);9      }10    } else {11      for (int i = 1; i <= rounds[m]; ++i) {12        ans.add(i);13      }14      for (int i = rounds[0]; i <= n; ++i) {15        ans.add(i);16      }17    }18    return ans;19  }20}

1class Solution {2public:3  vector<int> mostVisited(int n, vector<int> &rounds) {4    int m = rounds.size() - 1;5    vector<int> ans;6    if (rounds[0] <= rounds[m]) {7      for (int i = rounds[0]; i <= rounds[m]; ++i)8        ans.push_back(i);9    } else {10      for (int i = 1; i <= rounds[m]; ++i)11        ans.push_back(i);12      for (int i = rounds[0]; i <= n; ++i)13        ans.push_back(i);14    }15    return ans;16  }17};

1class Solution:2    def mostVisited(self, n: int, rounds: List[int]) -> List[int]: if rounds[0] <= rounds[- 1]: return list(range(rounds[0], rounds[- 1] + 1)) return list(range(1, rounds[- 1] + 1)) + list(range(rounds[0], n + 1))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem