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

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

Description Hints 3 Solution Video 8:41

2113. Elements in Array After Removing and Replacing Elements

Q: 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.

Q: 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.

Medium69.1% acceptancePremium elsewhere, free here

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] = [time_j, index_j]. The answer to the j^th query is:

nums[index_j] if index_j < nums.length at minute time_j
-1 if index_j >= nums.length at minute time_j

Return an integer array ans of size n where ans[j] is the answer to the j^th 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 <= 10⁵
queries[j].length == 2
0 <= time_j <= 10⁵
0 <= index_j < nums.length

Topics

Array

Hints open one at a time

Hint 1

Try to find a pattern in how nums changes.

Hint 2

Let m be the original length of nums. If time_i / m (integer division) is even, then nums is at its original size or decreasing in size. If it is odd, then it is empty, or increasing in size.

Hint 3

time_i % m can be used to find how many elements are in nums at minute time_i.

8:41

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[0,1,2]
[[0,2],[2,0],[3,2],[5,0]]

Input

[2]
[[0,0],[1,0],[2,0],[3,0]]

Your code is saved on this device.Solution