LeetCode 2113 - Elements in Array After Removing and Replacing Elements

The problem describes an array that continuously goes through a repeating two-phase process. At minute 0, the array is unchanged. Every following minute, the leftmost element is removed until the array becomes empty.

leetcodemediumarray

LeetCode Problem 2113

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem describes an array that continuously goes through a repeating two-phase process.

At minute 0, the array is unchanged. Every following minute, the leftmost element is removed until the array becomes empty. Once the array is empty, elements are added back one by one to the end of the array in the exact order they were removed. After the original array is fully restored, the entire process repeats forever.

For example, if:

nums = [0,1,2]

the sequence of states becomes:

Minute 0: [0,1,2]
Minute 1: [1,2]
Minute 2: [2]
Minute 3: []
Minute 4: [0]
Minute 5: [0,1]
Minute 6: [0,1,2]
Minute 7: [1,2]
...

Each query contains two integers:

[time, index]

For a given minute time, we must determine what the array looks like at that exact moment. If index exists in the current array, we return the value at that position. Otherwise, we return -1.

The important observation is that the array state repeats in cycles. If the original array has length m, then:

  • Removing all elements takes m minutes.
  • Re-adding all elements takes another m minutes.

Therefore, the process repeats every 2 * m minutes.

The constraints are small for the array itself:

1 <= nums.length <= 100

but the number of queries can be large:

1 <= queries.length <= 100000

This tells us that we cannot afford to simulate the process minute by minute for every query independently. Instead, we need a direct mathematical way to determine the array state at any time.

Several edge cases are especially important:

  • Arrays of length 1
  • Queries during the completely empty state
  • Queries exactly at cycle boundaries
  • Queries with very large time values
  • Queries where the requested index is larger than the current array size

The problem guarantees that:

0 <= indexj < nums.length

so the queried index is always valid relative to the original array, though it may not exist at the queried time.

Approaches

Brute Force Approach

A straightforward approach is to literally simulate the process minute by minute.

We could maintain the current array state and repeatedly:

  1. Remove the leftmost element until the array becomes empty.
  2. Append removed elements back in order.
  3. Repeat forever.

For every query, we would simulate the array up to the requested time and then check the queried index.

This approach is correct because it exactly follows the rules of the problem. However, it is inefficient because the query times can be as large as 100000, and there can be up to 100000 queries.

If we simulated independently for every query, the complexity would become far too large.

Optimal Approach

The key insight is that the process is completely periodic.

If the original array length is m, then:

  • The shrinking phase lasts m minutes.
  • The rebuilding phase lasts another m minutes.

Therefore, the entire process repeats every:

2 * m

minutes.

Instead of simulating every minute, we can reduce each query time using modulo arithmetic:

phase = time % (2 * m)

Now we only need to analyze where the array is within one cycle.

There are two cases:

  1. Removal phase, phase < m
  2. Rebuilding phase, phase >= m

During the removal phase:

Current array = nums[phase:]

because the first phase elements have been removed.

During the rebuilding phase:

added = phase - m
Current array = nums[:added]

because the first added elements have been restored.

Once we know the current array size and mapping, answering a query becomes constant time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(q × t) O(m) Simulates every minute for every query
Optimal O(q) O(1) Uses cycle periodicity and direct indexing

Here:

  • q is the number of queries
  • t is the maximum queried time
  • m is nums.length

Algorithm Walkthrough

  1. Compute the original array length m.

The entire process depends on the array size because one full cycle consists of removing all m elements and then restoring all m elements. 2. Compute the cycle length.

A complete cycle takes:

cycle = 2 * m
  1. Process each query independently.

Since queries do not affect each other, we can answer them one at a time. 4. Reduce the query time into a single cycle.

Compute:

phase = time % cycle

This tells us where we are inside the repeating pattern. 5. Determine whether we are in the removal phase or rebuilding phase.

If:

phase < m

then we are removing elements.

Otherwise, we are rebuilding the array. 6. Handle the removal phase.

After removing phase elements from the front:

current array = nums[phase:]

The current size becomes:

size = m - phase

If the queried index is outside this size, return -1.

Otherwise:

answer = nums[phase + index]
  1. Handle the rebuilding phase.

Compute:

restored = phase - m

This means the first restored elements have been added back.

The current array becomes:

nums[:restored]

If the queried index is outside this size, return -1.

Otherwise:

answer = nums[index]
  1. Store each answer in the result array.
  2. Return the final answers.

Why it works

The algorithm works because the array evolution is entirely deterministic and periodic. Every cycle repeats exactly after 2 * m minutes. Within a cycle, the removal phase always corresponds to a suffix of the original array, and the rebuilding phase always corresponds to a prefix of the original array. By directly computing which phase a query belongs to, we can determine the correct value without simulation.

Python Solution

from typing import List

class Solution:
    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        cycle_length = 2 * n

        answers = []

        for time, index in queries:
            phase = time % cycle_length

            # Removal phase
            if phase < n:
                current_size = n - phase

                if index >= current_size:
                    answers.append(-1)
                else:
                    answers.append(nums[phase + index])

            # Rebuilding phase
            else:
                restored = phase - n
                current_size = restored

                if index >= current_size:
                    answers.append(-1)
                else:
                    answers.append(nums[index])

        return answers

The implementation begins by computing the original array length and the total cycle length. Since the process repeats every 2 * n minutes, every query time can be reduced using modulo arithmetic.

For each query, the code determines whether the current moment belongs to the removal phase or rebuilding phase.

During the removal phase, the first phase elements have already been removed, so the remaining array starts at nums[phase]. If the requested index exceeds the current size, the answer is -1. Otherwise, the correct element is located at nums[phase + index].

During the rebuilding phase, the array consists of the first restored elements of the original array. Again, the index is checked against the current size before retrieving the value.

The solution processes each query independently in constant time.

Go Solution

func elementInNums(nums []int, queries [][]int) []int {
	n := len(nums)
	cycleLength := 2 * n

	answers := make([]int, 0, len(queries))

	for _, query := range queries {
		time := query[0]
		index := query[1]

		phase := time % cycleLength

		// Removal phase
		if phase < n {
			currentSize := n - phase

			if index >= currentSize {
				answers = append(answers, -1)
			} else {
				answers = append(answers, nums[phase+index])
			}
		} else {
			// Rebuilding phase
			restored := phase - n
			currentSize := restored

			if index >= currentSize {
				answers = append(answers, -1)
			} else {
				answers = append(answers, nums[index])
			}
		}
	}

	return answers
}

The Go implementation follows the exact same logic as the Python version. Since Go slices already provide indexed access in constant time, no additional data structures are necessary.

One small implementation detail is that the result slice is preallocated with capacity equal to the number of queries, which avoids repeated reallocations during appends.

Integer overflow is not a concern because all values are comfortably within Go's standard integer range.

Worked Examples

Example 1

nums = [0,1,2]
queries = [[0,2],[2,0],[3,2],[5,0]]

The array length is:

n = 3
cycle length = 6
Query phase Current Array index Answer
[0,2] 0 [0,1,2] 2 2
[2,0] 2 [2] 0 2
[3,2] 3 [] 2 -1
[5,0] 5 [0,1] 0 0

Final result:

[2,2,-1,0]

Example 2

nums = [2]
queries = [[0,0],[1,0],[2,0],[3,0]]

The array length is:

n = 1
cycle length = 2
Query phase Current Array index Answer
[0,0] 0 [2] 0 2
[1,0] 1 [] 0 -1
[2,0] 0 [2] 0 2
[3,0] 1 [] 0 -1

Final result:

[2,-1,2,-1]

Complexity Analysis

Measure Complexity Explanation
Time O(q) Each query is answered in constant time
Space O(1) Ignoring output storage, only a few variables are used

The algorithm performs a constant amount of work per query. No simulation or auxiliary data structure proportional to the input size is required. The output array itself requires O(q) space, but auxiliary space usage remains constant.

Test Cases

from typing import List

class Solution:
    def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        cycle_length = 2 * n

        answers = []

        for time, index in queries:
            phase = time % cycle_length

            if phase < n:
                current_size = n - phase

                if index >= current_size:
                    answers.append(-1)
                else:
                    answers.append(nums[phase + index])
            else:
                restored = phase - n
                current_size = restored

                if index >= current_size:
                    answers.append(-1)
                else:
                    answers.append(nums[index])

        return answers

sol = Solution()

# Provided example 1
assert sol.elementInNums(
    [0, 1, 2],
    [[0, 2], [2, 0], [3, 2], [5, 0]]
) == [2, 2, -1, 0]

# Provided example 2
assert sol.elementInNums(
    [2],
    [[0, 0], [1, 0], [2, 0], [3, 0]]
) == [2, -1, 2, -1]

# Single element repeated cycles
assert sol.elementInNums(
    [5],
    [[0, 0], [10, 0], [11, 0]]
) == [5, 5, -1]

# Query during empty state
assert sol.elementInNums(
    [1, 2, 3],
    [[3, 0], [3, 1], [3, 2]]
) == [-1, -1, -1]

# Rebuilding phase
assert sol.elementInNums(
    [4, 5, 6],
    [[4, 0], [5, 1]]
) == [4, 5]

# Large time values
assert sol.elementInNums(
    [7, 8],
    [[100000, 0], [100001, 0]]
) == [7, -1]

# Index out of current bounds
assert sol.elementInNums(
    [9, 10, 11],
    [[1, 2], [2, 1]]
) == [-1, -1]

# Full cycle reset
assert sol.elementInNums(
    [1, 2],
    [[0, 0], [4, 0], [8, 1]]
) == [1, 1, 2]

# Mixed phases
assert sol.elementInNums(
    [3, 6, 9],
    [[1, 0], [2, 0], [4, 0], [5, 1]]
) == [6, 9, 3, 6]
Test Why
Example 1 Validates standard removal and rebuilding
Example 2 Validates smallest possible array
Single element repeated cycles Ensures periodic behavior works correctly
Query during empty state Verifies handling of zero-length array state
Rebuilding phase Confirms correct restoration logic
Large time values Ensures modulo cycle logic is correct
Index out of current bounds Validates proper -1 handling
Full cycle reset Confirms exact cycle repetition
Mixed phases Tests transitions between phases

Edge Cases

One important edge case is an array of length 1. In this situation, the cycle alternates between a full array and an empty array every minute. Many incorrect implementations accidentally mishandle the rebuilding phase because the array immediately returns after becoming empty. The implementation handles this naturally through modulo arithmetic and phase detection.

Another critical edge case occurs when the array is completely empty. This happens exactly at minute n within each cycle. During this moment, every queried index must return -1. The implementation correctly computes the current size as zero, causing all indices to fail the bounds check.

Large query times are also important. Since timej can be as large as 100000, directly simulating the process would be inefficient. The implementation avoids this issue entirely by reducing every time value modulo the cycle length. This guarantees efficient constant-time processing regardless of how large the time becomes.

A final subtle case is when the queried index exists in the original array but not in the current array state. For example:

nums = [1,2,3]
time = 2
current array = [3]

In this state, only index 0 exists. Queries for indices 1 or 2 must return -1. The implementation explicitly checks the current array size before accessing elements, preventing invalid indexing and ensuring correctness.