We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Elements in Array After Removing and Replacing Elements

Number: 2258

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an integer array nums, at minute 0 the array remains unchanged. Then every minute the leftmost element is removed until the array becomes empty. After that, starting from the next minute, one element (in the same order they were removed) is appended at the end each minute until the original array is restored. This process repeats indefinitely. For a set of queries where each query is given as [time, index], determine the element at that index in the array at the given minute (or return -1 if such an index does not exist).

Key Insights

  • The process is cyclic with a period of 2 * n (n equals the length of nums).
  • For minutes in the removal phase (minute t where 1 ≤ t ≤ n), the array becomes nums[t:].
  • For minutes in the addition phase (minute t where n+1 ≤ t < 2n), the array is built up from the removed elements in order, i.e. the state is nums[0:(t - n)].
  • Use modulo arithmetic (t mod (2*n)) to compute the effective minute within the cycle.
  • Determine the current state size and then check if the requested index exists.

Space and Time Complexity

Time Complexity: O(1) per query, so overall O(q) where q is the number of queries.
Space Complexity: O(1), aside from the output array.

Solution

We first compute the length of the input array (n) and calculate the period (2*n). For each query [time, index]:

  1. Compute the effective minute m = time mod (2*n).
  2. If m is zero, the array state is the full original array.
  3. If 1 ≤ m ≤ n, the process is in the removal phase so the state is nums[m:]; therefore, the state size is n - m.
  4. If n < m < 2*n, the process is in the addition phase so the state is the first (m - n) elements of nums.
  5. Finally, check if the requested index is within the bounds of the current state. If yes, compute the element accordingly; if not, return -1.

This approach uses simple arithmetic and indexing to answer each query in constant time.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def solveQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)                      # Total number of elements in original array
        cycle = 2 * n                      # The process repeats every 2*n minutes
        results = []                       # List to store answers for each query
        
        for time, index in queries:
            m = time % cycle               # Effective minute within the cycle
            # Case 1: Full array state (m == 0)
            if m == 0:
                # Since the state is the full array, answer is nums[index] if index is in bounds
                if index < n:
                    results.append(nums[index])
                else:
                    results.append(-1)
            # Case 2: Removal phase (1 <= m <= n)
            elif m <= n:
                state_size = n - m         # Number of elements remaining after m removals
                if index < state_size:
                    # Element in current state is the one at position m + index in the original array
                    results.append(nums[m + index])
                else:
                    results.append(-1)
            # Case 3: Addition phase (n < m < 2*n)
            else:
                state_size = m - n         # Number of elements have been appended so far
                if index < state_size:
                    # The state is built from the appended elements in original order
                    results.append(nums[index])
                else:
                    results.append(-1)
        
        return results
← Back to All Questions