1560. Most Visited Sector in a Circular Track
Problem Description
In this problem, we have a circular track with n
sectors, each labeled from 1
to n
. A marathon is taking place on this track, consisting of m
rounds. Each round starts and ends at specified sectors, with the starting sector for each round given in an array rounds
. Specifically, the i
th round starts at sector rounds[i - 1]
and ends at sector rounds[i]
. The goal is to find out which sectors are the most visited throughout the marathon and return these sectors sorted in ascending order. It's important to notice that the sectors must be visited in the counter-clockwise direction and we wrap around the track each time we reach sector n
.
Intuition
The solution to this problem relies on the observation that if the start sector of the marathon (rounds[0]
) is less than or equal to the end sector (rounds[-1]
), then all sectors in between are visited more frequently than any other sector. This is because each round always moves from a lower to a higher sector number, covering all sectors in between.
However, if the start sector is greater than the end sector, this indicates that the runners have passed the sector marked n
and started a new lap, visiting the sectors from 1
to rounds[-1]
again. Therefore, in this case, the most visited sectors will be from sector 1
to rounds[-1]
and from rounds[0]
to sector n
.
The solution approach, therefore, is to check the relative positions of the start and end sectors and return the appropriate range of sectors:
- If
rounds[0]
is less than or equal torounds[-1]
, return a list of sectors ranging fromrounds[0]
torounds[-1]
. - If
rounds[0]
is greater thanrounds[-1]
, there are two ranges of sectors to consider. Combine the range from1
torounds[-1]
with the range fromrounds[0]
ton
into a single list and return it.
This insight leads to a straightforward solution that is intuitive and elegant, avoiding cumbersome calculations or tracking of the exact number of visits to each sector.
Solution Approach
The solution for finding the most visited sectors on the circular track follows a straightforward approach based on conditional logic rather than elaborate algorithms or data structures.
Here's a step-by-step explanation of the implementation:
-
Condition Check: First, we check if
rounds[0]
, the starting sector of the first round, is less than or equal torounds[-1]
, the ending sector of the last round.- If this condition is
True
, it means that the runners have not crossed the sector markedn
from the last round to the first round, so we only need to consider the sectors that lie betweenrounds[0]
androunds[-1]
.
- If this condition is
-
Range Construction (No Wrap-Around): When
rounds[0] <= rounds[-1]
:- We use the
range
function to generate a list starting fromrounds[0]
torounds[-1]
, inclusive. This list represents the sectors that are covered in a direct path from the starting sector to the ending sector without any wrap-around.
- We use the
-
Range Construction (With Wrap-Around): When
rounds[0] > rounds[-1]
:- This indicates that during the marathon, runners have wrapped around the track, passing by sector
n
and back to sector1
. We need to consider two ranges of sectors. - The first range is from sector
1
torounds[-1]
, inclusive, which represents the sectors visited after the last wrap-around. - The second range is from
rounds[0]
to sectorn
, inclusive, which represents the sectors visited before the wrap-around occurs. - These two ranges are combined to form a complete list of the most visited sectors.
- This indicates that during the marathon, runners have wrapped around the track, passing by sector
-
List Concatenation: To combine the two ranges when there is a wrap-around:
- We utilize list concatenation to join the lists resulting from the two
range
calls into a single list, which is returned as the final result.
- We utilize list concatenation to join the lists resulting from the two
The code implementation uses only basic Python constructs such as conditional statements and list manipulations, thereby avoiding the need for complex algorithms or data structures. It leverages Python's range
function to create lists directly corresponding to the ranges of sectors that are most visited, as deduced from the initial condition checks.
1class Solution:
2 def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
3 if rounds[0] <= rounds[-1]:
4 return list(range(rounds[0], rounds[-1] + 1))
5 else:
6 return list(range(1, rounds[-1] + 1)) + list(range(rounds[0], n + 1))
The function mostVisited
takes two parameters, n
and rounds
, which represent the number of sectors and the array of rounds, respectively. Within the function, we apply the logic outlined above to determine the most visited sectors and return them as a list.
The beauty of this solution lies in its simplicity and efficiency. Since it avoids additional computation by directly identifying the range of most visited sectors, it executes in constant time, making it suitable for even large values of n
and numbers of rounds.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using a circular track with 5
sectors (n = 5
) and an array of rounds [1, 3, 5, 2]
. We apply the steps from the solution approach to determine the most visited sectors.
Given:
n = 5
(sectors are 1, 2, 3, 4, 5)rounds = [1, 3, 5, 2]
We start by applying the first step in our solution approach.
-
Condition Check: We compare
rounds[0]
torounds[-1]
(we check whether1 <= 2
).- In this case, the condition is
True
because1
is less than2
. - Normally, this would imply that we only need to consider the sectors that lie between
1
and2
. However, since there is a wrap-around implied by the progression of sectors in the rounds from5
back to2
, we need to consider the full marathon sequence.
- In this case, the condition is
-
Range Construction (With Wrap-Around): Since
rounds[0]
is not greater thanrounds[-1]
but there is a wrap-around from the third to the fourth round (from5
back to2
), we consider the entire sequence of sectors visited.- The first range is from sector
1
to sector5
, inclusive. - The second range starts again at
1
after wrapping around and ends at2
.
- The first range is from sector
-
List Concatenation: We combine the ranges from the first round and after the wrap-around:
- The sectors visited are initially
[1, 2, 3, 4, 5]
, and following the wrap-around, the sectors[1, 2]
are visited again, leading to the sequence[1, 2, 3, 4, 5, 1, 2]
. - Since sectors
1
and2
were visited in the last part of the marathon, they would be added to the most visited sectors list.
- The sectors visited are initially
Hence, after evaluating the rounds in order, we determine that the most visited sectors would be [1, 2, 3, 4, 5]
, but [1, 2]
have the highest visit count due to the wrap-around. We need to sort them to return the result as [1, 2]
.
Using the given solution code, the mostVisited
function would thus return [1, 2, 3, 4, 5] + [1, 2]
, which simplifies to [1, 2, 3, 4, 5]
since we are asked to return unique sectors visited. After sorting, the final answer remains [1, 2, 3, 4, 5]
, since all sectors are most visited due to the marathon sequence that was provided in the rounds
array.
Solution Implementation
1class Solution:
2 def mostVisited(self, sector_count: int, rounds: List[int]) -> List[int]:
3 # The first sector visited in the first round
4 start_sector = rounds[0]
5 # The last sector visited in the last round
6 end_sector = rounds[-1]
7
8 # If the race started (start_sector) and ended (end_sector) on the same or a directly subsequent sector,
9 # or if the race direction was such that there was no wraparound
10 if start_sector <= end_sector:
11 # The most visited sectors are all sectors from start_sector to end_sector, inclusive
12 return list(range(start_sector, end_sector + 1))
13 else:
14 # If there was a wraparound, the most visited sectors are from the beginning (sector 1)
15 # to the end_sector, and from the start_sector to the end of the track (sector_count)
16 return list(range(1, end_sector + 1)) + list(range(start_sector, sector_count + 1))
17
18# Note: The List type needs to be imported from the typing module, so we should add the following line
19# at the beginning of the file:
20# from typing import List
21```
22
23Make sure to import the `List` type from the `typing` module for type annotations if it is not already imported:
24
25```python
26from typing import List
27
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public List<Integer> mostVisited(int sectors, int[] rounds) {
6 // The final round (m is now finalRoundIndex for clarity)
7 int finalRoundIndex = rounds.length - 1;
8 // List to store the most visited sectors
9 List<Integer> mostVisitedSectors = new ArrayList<>();
10
11 // If the first round is less than or equals to the last round, it means the path doesn't cross sector 1
12 if (rounds[0] <= rounds[finalRoundIndex]) {
13 // Iterate from start sector to end sector and add to the list
14 for (int i = rounds[0]; i <= rounds[finalRoundIndex]; ++i) {
15 mostVisitedSectors.add(i);
16 }
17 } else { // The path crosses sector 1
18 // Add sectors from 1 to the final round's sector
19 for (int i = 1; i <= rounds[finalRoundIndex]; ++i) {
20 mostVisitedSectors.add(i);
21 }
22 // Add sectors from the starting round's sector to the last sector (wrapping around)
23 for (int i = rounds[0]; i <= sectors; ++i) {
24 mostVisitedSectors.add(i);
25 }
26 }
27
28 // Return the list of most visited sectors
29 return mostVisitedSectors;
30 }
31}
32
1#include <vector>
2
3class Solution {
4public:
5 // This function returns the most visited sectors in a circular track after all rounds are completed.
6 std::vector<int> mostVisited(int totalSectors, std::vector<int>& rounds) {
7 int lastRoundIndex = rounds.size() - 1; // Get the index of the last round
8 std::vector<int> mostVisitedSectors; // Vector to store the most visited sectors
9
10 // Check if the starting sector number is less than or equal to the ending sector number
11 if (rounds[0] <= rounds[lastRoundIndex]) {
12 // If it is, add all sectors from the start sector to the end sector to the answer
13 for (int i = rounds[0]; i <= rounds[lastRoundIndex]; ++i) {
14 mostVisitedSectors.push_back(i);
15 }
16 } else {
17 // If it's not, the path has lapped around the track
18 // Add all sectors from 1 to the end sector
19 for (int i = 1; i <= rounds[lastRoundIndex]; ++i) {
20 mostVisitedSectors.push_back(i);
21 }
22 // Also add all sectors from the start sector to the total number of sectors
23 for (int i = rounds[0]; i <= totalSectors; ++i) {
24 mostVisitedSectors.push_back(i);
25 }
26 }
27 // Return the list of the most visited sectors after all the rounds
28 return mostVisitedSectors;
29 }
30};
31
1// Define the function to calculate the most visited sectors.
2// Take the total number of sectors and an array of rounds as inputs.
3function mostVisited(totalSectors: number, rounds: number[]): number[] {
4 // Get the index of the last round
5 const lastRoundIndex = rounds.length - 1;
6 // Initialize an array to store the most visited sectors
7 let mostVisitedSectors: number[] = [];
8
9 // Check if the starting sector number is less than or equal to the ending sector number
10 if (rounds[0] <= rounds[lastRoundIndex]) {
11 // Add all sectors from the start sector to the end sector to the most visited sectors
12 for (let i = rounds[0]; i <= rounds[lastRoundIndex]; i++) {
13 mostVisitedSectors.push(i);
14 }
15 } else {
16 // The path has lapped around the track, so cover both segments of the lap
17
18 // Add all sectors from 1 to the end sector number
19 for (let i = 1; i <= rounds[lastRoundIndex]; i++) {
20 mostVisitedSectors.push(i);
21 }
22
23 // Add all sectors from the start sector to the total number of sectors
24 for (let i = rounds[0]; i <= totalSectors; i++) {
25 mostVisitedSectors.push(i);
26 }
27 }
28
29 // Return the array of the most visited sectors
30 return mostVisitedSectors;
31}
32
Time and Space Complexity
The time complexity of the code is primarily determined by the creation of the list that gets returned. This involves generating a range of integers, which can be done in constant time for each integer in the range, and then converting that range into a list.
-
In the best-case scenario, where
rounds[0] <= rounds[-1]
, we create a single range fromrounds[0]
torounds[-1]
, which includes at mostn
elements. Thus, the time complexity for this case isO(n)
. -
In the worst-case scenario, where
rounds[0] > rounds[-1]
, we create two ranges. The first is from1
torounds[-1]
and the second is fromrounds[0]
ton
. In the worst case, these two ranges can also include up ton
elements combined, so the time complexity remainsO(n)
.
The space complexity of the code is determined by the space needed to store the output list.
- In both cases mentioned above, the space complexity depends on the number of elements in the output list, which can be at most
n
. Thus, the space complexity for the algorithm isO(n)
.
Therefore, the final time complexity is O(n)
and the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.