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] if indexj < nums.length at minute timej
  • -1 if indexj >= nums.length at minute timej

Return _an integer arrayans of size _n whereans[j]is the answer to thejth query.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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:

 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] - 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 <= 100
  • 0 <= nums[i] <= 100
  • n == queries.length
  • 1 <= n <= 10^5
  • queries[j].length == 2
  • 0 <= timej <= 10^5
  • 0 <= 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

  1. Let n be the length of nums.
  2. For each query [t, idx]:
    • Compute cycle = t % (2 * n).
    • If cycle < n, we are in the removal phase:
      • The array has n - cycle elements, starting from index cycle.
      • If idx >= n - cycle, return -1.
      • Else, the value is nums[cycle + idx].
    • Else, we are in the restoration phase:
      • The array has cycle - n + 1 elements, which are the first cycle - n + 1 elements of nums.
      • If idx >= cycle - n + 1, return -1.
      • Else, the value is nums[idx].
  3. Collect answers for all queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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) where q is the number of queries. Each query is processed in constant time.
  • 🧺 Space complexity: O(q) for the output array.