Elements in Array After Removing and Replacing Elements

Elements in Array After Removing and Replacing Elements - Problem

Array Medium

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.

Input & Output

Example 1 — Basic Cycle

$ Input: nums = [0,1,2], queries = [[3,1],[4,2]]

› Output: [-1,-1]

💡 Note: At time 3: array is [], so index 1 doesn't exist → -1. At time 4: array is [0], so index 2 doesn't exist → -1

Example 2 — Removal Phase

$ Input: nums = [2], queries = [[0,0],[1,0]]

› Output: [2,-1]

💡 Note: At time 0: array is [2], index 0 exists → 2. At time 1: array is [], index 0 doesn't exist → -1

Example 3 — Multiple Cycles

$ Input: nums = [1,2], queries = [[4,0],[6,1]]

› Output: [1,2]

💡 Note: Cycle length is 4. At time 4 (4%4=0): back to original [1,2], index 0 → 1. At time 6 (6%4=2): restoration phase → 2

Constraints

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
1 ≤ queries.length ≤ 5000
0 ≤ time_j ≤ 10⁹
0 ≤ index_j ≤ nums.length - 1

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is recognizing the array follows a predictable 2n-minute cycle: n minutes of removal followed by n minutes of restoration. Best approach uses modular arithmetic to directly calculate array state without simulation. Time: O(m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(m × t)	O(n)	Simulate each minute by actually modifying the array
Mathematical Pattern Recognition	O(m)	O(1)	Calculate array state using mathematical formulas instead of simulation

Brute Force Simulation — Algorithm Steps

Step 1: For each query, start from initial array
Step 2: Simulate each minute up to query time
Step 3: Check if index exists and return value or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with original array [0,1,2]

Simulate Minutes

Remove left elements then restore them

Query Result

Check if index exists at target time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int time = queries[i][0];
        int index = queries[i][1];
        
        // Create copy of original array
        int* current = (int*)malloc(numsSize * sizeof(int));
        int currentSize = numsSize;
        for (int j = 0; j < numsSize; j++) {
            current[j] = nums[j];
        }
        
        // Simulate each minute
        for (int minute = 0; minute < time; minute++) {
            if (currentSize > 0) {
                // Remove leftmost
                for (int j = 0; j < currentSize - 1; j++) {
                    current[j] = current[j + 1];
                }
                currentSize--;
            } else {
                // Restoration phase - add back elements
                int restoreIndex = minute % numsSize;
                current[currentSize] = nums[restoreIndex];
                currentSize++;
            }
        }
        
        // Check if index exists
        if (index < currentSize) {
            result[i] = current[index];
        } else {
            result[i] = -1;
        }
        
        free(current);
    }
    
    return result;
}

int main() {
    // Simple parsing for demo
    int nums[] = {0, 1, 2};
    int numsSize = 3;
    
    int query1[] = {3, 1};
    int query2[] = {4, 2};
    int* queries[] = {query1, query2};
    int queriesColSize[] = {2, 2};
    int queriesSize = 2;
    
    int returnSize;
    int* result = solution(nums, numsSize, queries, queriesSize, queriesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × t)

m queries × maximum time t, simulating each minute

✓ Linear Growth

Space Complexity

O(n)

Copy of original array for simulation

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

284 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler