Skip to main content
Talentd

Elements in Array After Removing and Replacing Elements - Solution & Explanation

MediumPremiumFree on FleetCodeArray10 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solution

First, we initialize an array ans with length m to store the answers, initializing all elements to -1.

Next, we iterate through the array queries. For each query, we first obtain the current query time t and index i. We then take t modulo 2n and compare t with n:

  • If t < n, then the number of array elements at time t is n - t, and the array elements are the result of the original array elements shifted left by t positions. Therefore, if i < n - t, the answer is nums[i + t];
  • If t > n, then the number of array elements at time t is t - n, and the array elements are the first t - n elements of the original array. Therefore, if i < t - n, the answer is nums[i].

Finally, return the array ans.

The time complexity is O(m), where m is the length of the array queries. Ignoring the space consumed by the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n * q)O(n)Good for understanding the process or when constraints are small
Direct CalculationO(q)O(1)Best approach for large inputs; compute the array state mathematically per query

Video Solution

2113. Elements in Array After Removing and Replacing Elements (Leetcode Medium) • Programming Live with Larry • 235 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Elements in Array After Removing and Replacing Elements easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 70%. The challenge is recognizing the predictable pattern of removals and insertions so you can replace simulation with constant-time calculations.
Elements in Array After Removing and Replacing Elements Python/Java solution
Most implementations follow the same logic across languages. For each query, check whether t < n or t >= n, compute the valid array size, and return the appropriate element from nums if the index is within bounds. This logic works identically in Python, Java, C++, Go, and TypeScript.
How to solve Elements in Array After Removing and Replacing Elements in O(n)?
Avoid simulating operations. Observe that during the first n steps the array becomes nums[t:], and after that it rebuilds as nums[0..t-n-1]. Using this pattern, each query can compute the correct element using simple index arithmetic without modifying the array.
What is the best approach for Elements in Array After Removing and Replacing Elements?
The direct calculation approach is the best solution. Instead of simulating each removal and insertion, compute which segment of the original array exists at time t. This allows each query to be answered in O(1) time with O(1) extra space.
Is Elements in Array After Removing and Replacing Elements asked at Google/Amazon/Meta?
Problems with array state transitions and query processing are common in interviews at companies like Google, Amazon, and Meta. Variants often test whether you replace brute force simulation with mathematical reasoning or prefix calculations.
What data structure is used in Elements in Array After Removing and Replacing Elements?
The optimal approach does not require additional data structures. The solution relies on direct array indexing and simple arithmetic to determine which element exists after a given number of operations.
What is the time complexity of Elements in Array After Removing and Replacing Elements?
The optimal solution processes each query in O(1) time using direct index calculations. If there are q queries, the total time complexity is O(q) with O(1) additional space. A brute force simulation can degrade to O(n * q).

Ready to solve this problem?

Practice Elements in Array After Removing and Replacing Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays