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:
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]
for0 <= i < m
Solution
/**
* @param {number} n
* @param {number[]} rounds
* @return {number[]}
*/
var mostVisited = function(n, rounds) {
var start = rounds[0];
var end = rounds[rounds.length - 1];
if (end >= start) {
return Array(end - start + 1).fill(0).reduce((arr, num, i) => {
arr.push(start + i);
return arr;
}, []);
} else {
var arr1 = Array(n - start + 1).fill(0).reduce((arr, num, i) => {
arr.push(start + i);
return arr;
}, []);
var arr2 = Array(end).fill(0).reduce((arr, num, i) => {
arr.push(i + 1);
return arr;
}, []);
return arr2.concat(arr1);
}
};
Explain:
if start <= end, return range[start, end]
else return range[0, end] + range[start, n]
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).