Scale Engineer

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

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.

import java.util.ArrayList;import java.util.List; public class Solution {    public List<Integer> mostVisited(int n, int[] rounds) {        int[] counts = new int[n + 1];                // The marathon starts at sector rounds[0].        // We count this initial position.        counts[rounds[0]]++;                // Simulate each round        for (int i = 0; i < rounds.length - 1; i++) {            int start = rounds[i];            int end = rounds[i+1];                        // Move from start to end, one sector at a time            int current = start;            while (current != end) {                current = (current == n) ? 1 : current + 1;                counts[current]++;            }        }                // Find the maximum number of visits        int maxVisits = 0;        for (int count : counts) {            if (count > maxVisits) {                maxVisits = count;            }        }                // Collect all sectors with the maximum number of visits        List<Integer> result = new ArrayList<>();        for (int i = 1; i <= n; i++) {            if (counts[i] == maxVisits) {                result.add(i);            }        }                return result;    }}

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.

Solutions

class Solution {public  List<Integer> mostVisited(int n, int[] rounds) {    int m = rounds.length - 1;    List<Integer> ans = new ArrayList<>();    if (rounds[0] <= rounds[m]) {      for (int i = rounds[0]; i <= rounds[m]; ++i) {        ans.add(i);      }    } else {      for (int i = 1; i <= rounds[m]; ++i) {        ans.add(i);      }      for (int i = rounds[0]; i <= n; ++i) {        ans.add(i);      }    }    return ans;  }}

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 →

Next problem