# Most Visited Sector in  a Circular Track
**Difficulty:** EASY
[External](https://leetcode.com/problems/most-visited-sector-in-a-circular-track)
Canonical: https://scaleengineer.com/dsa/problems/most-visited-sector-in-a-circular-track
**Data structures:** Array
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia)
---
## Problem
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:**

![](https://assets.glich.co/dsa/most-visited-sector-in-a-circular-track/image0.jpg) 

**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
## Full Simulation
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### 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`.

## Start and End Point Analysis
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.
**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`.
**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.
### Explanation
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:
1.  If `start <= end`, the path is a simple sequence: `start, start + 1, ..., end`.
2.  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`.
```java
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> mostVisited(int n, int[] rounds) {
        List<Integer> result = new ArrayList<>();
        int start = rounds[0];
        int end = rounds[rounds.length - 1];
        
        if (start <= end) {
            // Path does not wrap around
            for (int i = start; i <= end; i++) {
                result.add(i);
            }
        } else { // start > end
            // Path wraps around. Add segments to keep it sorted.
            // Segment 1: from 1 to end
            for (int i = 1; i <= end; i++) {
                result.add(i);
            }
            // Segment 2: from start to n
            for (int i = start; i <= n; i++) {
                result.add(i);
            }
        }
        
        return result;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> mostVisited(int n, vector<int> &rounds) {
    int m = rounds.size() - 1;
    vector<int> ans;
    if (rounds[0] <= rounds[m]) {
      for (int i = rounds[0]; i <= rounds[m]; ++i)
        ans.push_back(i);
    } else {
      for (int i = 1; i <= rounds[m]; ++i)
        ans.push_back(i);
      for (int i = rounds[0]; i <= n; ++i)
        ans.push_back(i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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))

```