Watch 2 video solutions for Elements in Array After Removing and Replacing Elements, a medium level problem involving Array. This walkthrough by Programming Live with Larry has 235 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
[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 timejReturn an integer array ans of size n where ans[j] is the answer to the jth query.
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 <= 105queries[j].length == 20 <= timej <= 1050 <= indexj < nums.lengthProblem Overview: You start with an array nums of size n. The system performs 2n operations: the first n remove elements from the front one by one, and the next n append the original elements back in order. Each query asks: what element exists at index i after operation t? If the index does not exist at that moment, return -1.
Approach 1: Brute Force Simulation (O(n) per query time, O(n) space)
The most straightforward way is to simulate the array changes step by step. Use a queue-like structure: repeatedly remove the first element during the first n operations, then append elements back during the next n. After each operation, store the resulting array state or answer queries directly. This approach mirrors the process exactly, which makes it easy to reason about. The downside is performance: every removal from the front shifts elements or requires a deque structure, and answering many queries becomes expensive. Total complexity can reach O(n * q) in the worst case.
Approach 2: Direct Calculation (O(1) per query time, O(1) space)
The array state follows a predictable pattern, so you never need to simulate operations. During the first n operations (t < n), the array is simply the suffix nums[t:]. Its size becomes n - t. If a query asks for index i and i < n - t, the answer is nums[t + i]. Otherwise the index is out of bounds.
After all elements are removed (t ≥ n), the array starts rebuilding from the original order. At time t, exactly t - n elements have been appended. The array becomes [nums[0], nums[1], ..., nums[t-n-1]]. If the queried index i is smaller than t - n, return nums[i]; otherwise return -1. Each query becomes a few arithmetic checks and a direct index lookup.
This observation eliminates all mutation and data structures. Instead of tracking the array state, you compute which portion of the original array is visible at time t. The result is constant time processing per query with zero extra memory.
Recommended for interviews: The direct calculation approach is what interviewers expect. Brute force simulation shows you understand the process, but recognizing the predictable structure of removals and insertions demonstrates stronger reasoning about array transformations and simulation patterns. Reducing the problem to simple index math is the key insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * q) | O(n) | Good for understanding the process or when constraints are small |
| Direct Calculation | O(q) | O(1) | Best approach for large inputs; compute the array state mathematically per query |