Elements in Array After Removing and Replacing Elements
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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]ifindexj < nums.lengthat minutetimej-1ifindexj >= nums.lengthat minutetimej
Return _an integer arrayans of size _n whereans[j]is the answer to thejth query.
Examples
Example 1:
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] - 0 is added to the end of nums.
Minute 5: [0,1] - 1 is added to the end of nums.
At minute 0, nums[2] is 2.
At minute 2, nums[0] is 2.
At minute 3, nums[2] does not exist.
At minute 5, nums[0] is 0.
Example 2:
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] - 2 is added to the end of nums.
Minute 3: [] - The leftmost element, 2, is removed.
At minute 0, nums[0] is 2.
At minute 1, nums[0] does not exist.
At minute 2, nums[0] is 2.
At minute 3, nums[0] does not exist.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100n == queries.length1 <= n <= 10^5queries[j].length == 20 <= timej <= 10^50 <= indexj < nums.length
Solution
Method 1 – Simulation and Cycle Math
Intuition
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.
Approach
- Let
nbe the length ofnums. - For each query
[t, idx]:- Compute
cycle = t % (2 * n). - If
cycle < n, we are in the removal phase:- The array has
n - cycleelements, starting from indexcycle. - If
idx >= n - cycle, return-1. - Else, the value is
nums[cycle + idx].
- The array has
- Else, we are in the restoration phase:
- The array has
cycle - n + 1elements, which are the firstcycle - n + 1elements ofnums. - If
idx >= cycle - n + 1, return-1. - Else, the value is
nums[idx].
- The array has
- Compute
- Collect answers for all queries.
Code
C++
class Solution {
public:
vector<int> elementInNums(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> ans;
for (auto& q : queries) {
int t = q[0], idx = q[1];
int cycle = t % (2 * n);
if (cycle < n) {
if (idx >= n - cycle) ans.push_back(-1);
else ans.push_back(nums[cycle + idx]);
} else {
int len = cycle - n + 1;
if (idx >= len) ans.push_back(-1);
else ans.push_back(nums[idx]);
}
}
return ans;
}
};
Go
func elementInNums(nums []int, queries [][]int) []int {
n := len(nums)
ans := make([]int, 0, len(queries))
for _, q := range queries {
t, idx := q[0], q[1]
cycle := t % (2 * n)
if cycle < n {
if idx >= n-cycle {
ans = append(ans, -1)
} else {
ans = append(ans, nums[cycle+idx])
}
} else {
l := cycle - n + 1
if idx >= l {
ans = append(ans, -1)
} else {
ans = append(ans, nums[idx])
}
}
}
return ans
}
Java
class Solution {
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;
}
}
Kotlin
class Solution {
fun elementInNums(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 + 1
if (idx >= len) ans.add(-1)
else ans.add(nums[idx])
}
}
return ans
}
}
Python
class Solution:
def elementInNums(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 + 1
if idx >= l:
ans.append(-1)
else:
ans.append(nums[idx])
return ans
Rust
impl Solution {
pub fn element_in_nums(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = nums.len();
let mut ans = Vec::with_capacity(queries.len());
for q in queries.iter() {
let t = q[0] as usize;
let idx = q[1] as usize;
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
}
}
TypeScript
class Solution {
elementInNums(nums: number[], queries: number[][]): number[] {
const n = nums.length;
const ans: number[] = [];
for (const [t, idx] of queries) {
const cycle = t % (2 * n);
if (cycle < n) {
if (idx >= n - cycle) ans.push(-1);
else ans.push(nums[cycle + idx]);
} else {
const l = cycle - n + 1;
if (idx >= l) ans.push(-1);
else ans.push(nums[idx]);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(q)whereqis the number of queries. Each query is processed in constant time. - 🧺 Space complexity:
O(q)for the output array.