You are given a 0-indexed integer array nums. Initially on minute 0, the array is unchanged. Every minute, the leftmost element in nums is removed until no elements remain. Then, every minute, one element is appended to the end of nums, in the order they were removed in, until the original array is restored. This process repeats indefinitely.
For example, the array [0,1,2] would change as follows: [0,1,2] -> [1,2] -> [2] -> [] -> [0] -> [0,1] -> [0,1,2] -> [1,2] -> [2] -> [] -> [0] -> [0,1] -> [0,1,2] -> ...
You are also given a 2D integer array queries of size n where queries[j] = [timej, indexj]. The answer to the jth query is:
nums[indexj] if indexj < nums.length at minute timej
-1 if indexj >= nums.length at minute timej
Return _an integer arrayans of size _nwhereans[j]is the answer to thejthquery.
Input: nums =[0,1,2], queries =[[0,2],[2,0],[3,2],[5,0]]Output: [2,2,-1,0]Explanation:
Minute 0:[0,1,2]- All elements are in the nums.Minute 1:[1,2]- The leftmost element,0,is removed.Minute 2:[2]- The leftmost element,1,is removed.Minute 3:[]- The leftmost element,2,is removed.Minute 4:[0]-0is added to the end of nums.Minute 5:[0,1]-1is added to the end of nums.At minute 0, nums[2]is2.At minute 2, nums[0]is2.At minute 3, nums[2] does not exist.At minute 5, nums[0]is0.
Example 2:
1
2
3
4
5
6
7
8
9
10
Input: nums =[2], queries =[[0,0],[1,0],[2,0],[3,0]]Output: [2,-1,2,-1]Minute 0:[2]- All elements are in the nums.Minute 1:[]- The leftmost element,2,is removed.Minute 2:[2]-2is added to the end of nums.Minute 3:[]- The leftmost element,2,is removed.At minute 0, nums[0]is2.At minute 1, nums[0] does not exist.At minute 2, nums[0]is2.At minute 3, nums[0] does not exist.
The process of removing and then restoring elements is periodic, with a cycle length of 2 * n (where n is the length of nums). For each minute, we can determine whether we are in the removal phase or the restoration phase, and compute the current array and answer accordingly without simulating every step.
classSolution {
public List<Integer>elementInNums(int[] nums, int[][] queries) {
int n = nums.length;
List<Integer> ans =new ArrayList<>();
for (int[] q : queries) {
int t = q[0], idx = q[1];
int cycle = t % (2 * n);
if (cycle < n) {
if (idx >= n - cycle) ans.add(-1);
else ans.add(nums[cycle + idx]);
} else {
int len = cycle - n + 1;
if (idx >= len) ans.add(-1);
else ans.add(nums[idx]);
}
}
return ans;
}
}
classSolution {
funelementInNums(nums: IntArray, queries: Array<IntArray>): List<Int> {
val n = nums.size
val ans = mutableListOf<Int>()
for (q in queries) {
val t = q[0]
val idx = q[1]
val cycle = t % (2 * n)
if (cycle < n) {
if (idx >= n - cycle) ans.add(-1)
else ans.add(nums[cycle + idx])
} else {
val len = cycle - n + 1if (idx >= len) ans.add(-1)
else ans.add(nums[idx])
}
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defelementInNums(self, nums: list[int], queries: list[list[int]]) -> list[int]:
n = len(nums)
ans = []
for t, idx in queries:
cycle = t % (2* n)
if cycle < n:
if idx >= n - cycle:
ans.append(-1)
else:
ans.append(nums[cycle + idx])
else:
l = cycle - n +1if idx >= l:
ans.append(-1)
else:
ans.append(nums[idx])
return ans
impl Solution {
pubfnelement_in_nums(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = nums.len();
letmut ans = Vec::with_capacity(queries.len());
for q in queries.iter() {
let t = q[0] asusize;
let idx = q[1] asusize;
let cycle = t % (2* n);
if cycle < n {
if idx >= n - cycle {
ans.push(-1);
} else {
ans.push(nums[cycle + idx]);
}
} else {
let l = cycle - n +1;
if idx >= l {
ans.push(-1);
} else {
ans.push(nums[idx]);
}
}
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
elementInNums(nums: number[], queries: number[][]):number[] {
constn=nums.length;
constans: number[] = [];
for (const [t, idx] ofqueries) {
constcycle=t% (2*n);
if (cycle<n) {
if (idx>=n-cycle) ans.push(-1);
elseans.push(nums[cycle+idx]);
} else {
constl=cycle-n+1;
if (idx>=l) ans.push(-1);
elseans.push(nums[idx]);
}
}
returnans;
}
}