Most Visited Sector in a Circular Track in Java
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.
Approach 1: Concatenated Wrap-Around Sector Counting
The Concatenated Wrap-Around Sector Counting approach is particularly useful when dealing with circular structures, such as circular race tracks or circular queues. To account for wrap-around movements, we concatenate the sequence of rounds with itself and this creates an extended sequence that includes all possible movements around the circular track without having to explicitly handle wrap-around logic.
Algorithm
Step 1: Take input rounds: An array representing the sequence of rounds, where each round specifies the starting sector of a movement around the circular track and n: An integer representing the total number of sectors on the circular track.
Step 2: Initialize an array visits of size n + 1 to keep track of the visit counts for each sector. Initialize all elements of visits to 0. Initialize an empty list mostVisitedSectors to store the sectors with the highest visit count.
Step 3: Initialize an integer variable maxVisits to keep track of the maximum visit count encountered.
Step 4: Concatenation of Rounds: Create a new list extendedRounds and copy the elements of the rounds array into it twice and this will create an extended sequence of rounds to handle wrap-around movements.
Step 5: Counting Visits: Iterate over the elements of the extendedRounds list from the second element (index 1) to the last element.
Step 6: For each pair of consecutive rounds (rounds[i-1] and rounds[i]), determine the starting sector start (minimum of the two sectors) and ending sector end (maximum of the two sectors).
Step 7: Increment the visit count for each sector in the range from start to end, inclusive, in the visits array.
Step 8: Identifying Most Visited Sectors: While counting visits for each sector, update maxVisits and mostVisitedSectors accordingly:
Step 9: If the visit count of a sector surpasses maxVisits, update maxVisits to the new maximum visit count and clear mostVisitedSectors. Add the current sector to mostVisitedSectors.
Step 10: If the visit count of a sector equals maxVisits and the sector is not already in mostVisitedSectors, add it to mostVisitedSectors.
Step 11: Sort the mostVisitedSectors list in ascending order. Return the sorted mostVisitedSectors list as the result.
Filename: CircularTrack.java
import java.util.*;
public class CircularTrack {
public static void main(String[] args) {
int[] rounds = {1, 3, 1, 2};
int n = 4; // Number of sectors
List<Integer> mostVisitedSectors = findMostVisitedSectors(rounds, n);
System.out.println("Most visited sectors: " + mostVisitedSectors);
}
public static List<Integer> findMostVisitedSectors(int[] rounds, int n) {
List<Integer> mostVisitedSectors = new ArrayList<>();
int maxVisits = 0;
// Concatenate rounds array to consider wrap-around
List<Integer> extendedRounds = new ArrayList<>();
for (int round : rounds) {
extendedRounds.add(round);
}
for (int round : rounds) {
extendedRounds.add(round);
}
// Iterate through the rounds and count visits to each sector
int[] visits = new int[n + 1]; // +1 to account for 1-based indexing
for (int i = 1; i < extendedRounds.size(); i++) {
int start = Math.min(extendedRounds.get(i - 1), extendedRounds.get(i));
int end = Math.max(extendedRounds.get(i - 1), extendedRounds.get(i));
for (int j = start; j <= end; j++) {
visits[j]++;
if (visits[j] > maxVisits) {
maxVisits = visits[j];
mostVisitedSectors.clear();
mostVisitedSectors.add(j);
} else if (visits[j] == maxVisits && !mostVisitedSectors.contains(j)) {
mostVisitedSectors.add(j);
}
}
}
// Sort the most visited sectors list
Collections.sort(mostVisitedSectors);
return mostVisitedSectors;
}
}
Output:
Most visited sectors: [1, 2]
Time Complexity
The time complexity of the algorithm is O(n * m), where n is the number of sectors and m is the total number of rounds in the rounds array and this complexity arises from iterating over each round and performing operations that take O(n) time, such as counting visits to each sector and updating visit counts.
Space Complexity
The space complexity of the algorithm is O(n), where n is the number of sectors, this complexity is due to the visits array, which stores the visit counts for each sector, and other auxiliary variables used in the algorithm.
Approach 2: Sweep Line Algorithm
The Sweep Line Algorithm involves moving a "sweep line" or "sweep ray" across the problem space, processing events as it moves. In the context of the circular track problem, the sweep line conceptually moves along the circular track, keeping track of the number of overlapping rounds at each sector. By employing the Sweep Line Algorithm, we can efficiently handle the wrap-around nature of the circular track while accurately identifying the most visited sectors.
Algorithm
Step 1: Take input of rounds: An array representing the sequence of rounds, where each round specifies the starting sector of a movement around the circular track and n: An integer representing the total number of sectors on the circular track.
Step 2: Initialize an array sectorCounts of size n + 1 to keep track of the visit counts for each sector. Initialize all elements of sectorCounts to 0.
Step 3: Initialize an empty list mostVisitedSectors to store the sectors with the highest visit count. Initialize an integer variable maxVisits to keep track of the maximum visit count encountered.
Step 4: Sort the rounds array to ensure that the start and end points of each round are in ascending order of their positions on the circular track.
Step 5: Process Rounds with Sweep Line: Iterate through the sorted rounds array, considering each round as a start point and its subsequent round as an end point.
Step 6: For each pair of consecutive rounds (rounds[i] and rounds[i+1]), determine the starting sector start and ending sector end of the movement. Handle wrap-around movements by adding n to the ending sector if it is less than the starting sector.
Step 7: Iterate over the sectors from start to end, inclusive, updating the visit count for each sector in the sectorCounts array.
Step 8: After processing all rounds, find the maximum visit count maxVisits in the sectorCounts array. Iterate over the sectorCounts array and add sectors with visit count equal to maxVisits to the mostVisitedSectors list.
Step 9: Return the mostVisitedSectors list containing the sectors with the highest visit count.
Filename: CircularTrack1.java
import java.util.*;
public class CircularTrack1 {
public static void main(String[] args) {
int[] rounds = {1, 3, 1, 2};
int n = 4; // Number of sectors
List<Integer> mostVisitedSectors = findMostVisitedSectors(rounds, n);
System.out.println("Most visited sectors: " + mostVisitedSectors);
}
public static List<Integer> findMostVisitedSectors(int[] rounds, int n) {
// Create an array to represent the circular track
int[] sectorCounts = new int[n + 1]; // +1 to account for 1-based indexing
// Sort the start and end points of rounds
Arrays.sort(rounds);
// Iterate through the sorted rounds and update sectorCounts
for (int i = 0; i < rounds.length - 1; i++) {
int start = rounds[i];
int end = rounds[i + 1];
if (end < start) {
end += n; // Handle wrap-around
}
for (int j = start; j <= end; j++) {
int sector = j % n;
if (sector == 0) {
sector = n; // Adjust for 1-based indexing
}
sectorCounts[sector]++;
}
}
// Find the maximum count of visits
int maxVisits = 0;
for (int count : sectorCounts) {
maxVisits = Math.max(maxVisits, count);
}
// Find the sectors with the maximum visit count
List<Integer> mostVisitedSectors = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (sectorCounts[i] == maxVisits) {
mostVisitedSectors.add(i);
}
}
return mostVisitedSectors;
}
}
Output:
Most visited sectors: [1, 2]
Time Complexity
The time complexity of the algorithm is O(m log m), where m is the total number of rounds, this complexity arises from the sorting step required to process the rounds in ascending order of their positions on the circular track.
Space Complexity
The space complexity of the algorithm is O(n), where n is the number of sectors, this complexity arises from the sectorCounts array used to store the visit counts for each sector.