Problem Description

You have an array nums of positive integers (0-indexed) and need to process a series of queries on it. Each element in the array starts as "unmarked".

For each query queries[i] = [index_i, k_i], you perform two steps:

1. Mark the element at position index_i (if it's not already marked)
2. Mark k_i additional unmarked elements that have the smallest values in the array
   • If multiple elements have the same smallest value, mark those with smaller indices first
   • If there are fewer than k_i unmarked elements remaining, mark all of them

After each query, you need to calculate the sum of all unmarked elements.

Example walkthrough:

If nums = [1, 2, 2, 1, 2, 3, 1] and queries = [[1, 2], [3, 3]]:

• Initially all elements are unmarked, sum = 12
• Query 1: [1, 2]
  • Mark element at index 1 (value = 2)
  • Mark 2 smallest unmarked elements: indices 0 and 3 (both have value 1)
  • Unmarked elements: indices 2, 4, 5, 6 with sum = 2 + 2 + 3 + 1 = 8
• Query 2: [3, 3]
  • Element at index 3 already marked, skip
  • Mark 3 smallest unmarked elements: index 6 (value 1), indices 2 and 4 (both value 2)
  • Unmarked element: only index 5 with sum = 3

Return [8, 3] as the answer array containing the sum of unmarked elements after each query.

Intuition

The key insight is that we need to efficiently find and mark the smallest unmarked elements repeatedly across multiple queries. If we try to search for the smallest unmarked elements every time we process a query, it would be inefficient.

Instead, we can preprocess the array by sorting all elements by their values (keeping track of their original indices). This gives us a global ordering of elements from smallest to largest. When we need to mark k smallest unmarked elements, we can simply traverse this sorted list from where we left off in the previous query.

Think of it like having a queue of people sorted by height. When asked to select the k shortest people who haven't been selected yet, we just go down the line from where we stopped last time, skipping anyone already selected, until we've picked k people.

The running sum optimization is straightforward - instead of recalculating the sum after each query, we maintain a running sum s that starts as the total sum of all elements. Whenever we mark an element, we subtract its value from s. This way, s always represents the current sum of unmarked elements.

The use of a boolean array mark to track which elements have been marked allows us to quickly check and update the marking status in O(1) time. The pointer j in the sorted array ensures we don't re-examine elements we've already processed, making the overall traversal through all queries linear with respect to the array size.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Initial Setup:

• Calculate the total sum s = sum(nums) which represents the sum of all unmarked elements initially
• Create a boolean array mark = [False] * n to track which elements are marked
• Create an array of tuples arr = [(value, index)] for each element in nums, then sort it by value first, and by index if values are equal. This gives us the global ordering we need.

2. Processing Queries: For each query [index, k]:

• Mark the specified index:

  if not mark[index]:
      mark[index] = True
      s -= nums[index]

  If the element at index hasn't been marked yet, mark it and subtract its value from the running sum.

• Mark k smallest unmarked elements:

  while k and j < n:
      if not mark[arr[j][1]]:
          mark[arr[j][1]] = True
          s -= arr[j][0]
          k -= 1
      j += 1

  We use a pointer j that persists across queries. Starting from where we left off, we traverse the sorted array arr:

  • Check if the element at original index arr[j][1] is unmarked
  • If unmarked, mark it and subtract its value arr[j][0] from the sum
  • Decrement k (one less element to mark)
  • Move j forward regardless of whether we marked the element or not

  The loop continues until either k reaches 0 (we've marked enough elements) or j reaches n (no more elements to check).

• Record the result: After processing the marking operations, append the current sum s to the answer array.

3. Return the answer array containing the sum of unmarked elements after each query.

Time Complexity: O(n log n + n + m) where n is the length of nums and m is the number of queries. The sorting takes O(n log n), and we traverse the sorted array at most once across all queries.

Space Complexity: O(n) for the sorted array and marking array.

Example Walkthrough

Let's trace through a small example to illustrate the solution approach.

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

Step 1: Initial Setup

• Calculate total sum: s = 5 + 3 + 3 + 2 = 13
• Create marking array: mark = [False, False, False, False]
• Create and sort array of (value, index) pairs:
  • Original pairs: [(5, 0), (3, 1), (3, 2), (2, 3)]
  • After sorting: arr = [(2, 3), (3, 1), (3, 2), (5, 0)]
• Initialize pointer: j = 0

Step 2: Process Query 1 - [0, 1]

• Mark element at index 0:
  • mark[0] is False, so mark it: mark = [True, False, False, False]
  • Subtract from sum: s = 13 - 5 = 8
• Mark k=1 smallest unmarked elements:
  • Start at j=0: arr[0] = (2, 3), index 3 is unmarked
    • Mark index 3: mark = [True, False, False, True]
    • Subtract from sum: s = 8 - 2 = 6
    • Decrement k: k = 0
    • Increment j: j = 1
  • k is now 0, so stop
• Record result: answer = [6]

Step 3: Process Query 2 - [3, 2]

• Mark element at index 3:
  • mark[3] is True (already marked), so skip
• Mark k=2 smallest unmarked elements:
  • Continue from j=1: arr[1] = (3, 1), index 1 is unmarked
    • Mark index 1: mark = [True, True, False, True]
    • Subtract from sum: s = 6 - 3 = 3
    • Decrement k: k = 1
    • Increment j: j = 2
  • Continue with j=2: arr[2] = (3, 2), index 2 is unmarked
    • Mark index 2: mark = [True, True, True, True]
    • Subtract from sum: s = 3 - 3 = 0
    • Decrement k: k = 0
    • Increment j: j = 3
  • k is now 0, so stop
• Record result: answer = [6, 0]

Final Answer: [6, 0]

The key insight demonstrated here is how the pointer j persists across queries, allowing us to efficiently find the next smallest unmarked elements without re-scanning the entire sorted array each time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + m), where n is the length of the array nums and m is the length of queries.

• Creating the sorted array arr with sorted((x, i) for i, x in enumerate(nums)) takes O(n × log n) time.
• The main loop iterates through each query in queries, which takes O(m) iterations.
• Within each query iteration:
  • Marking index and updating sum s takes O(1) time.
  • The inner while loop processes at most k elements, but crucially, the pointer j only moves forward throughout the entire execution, never resets.
• Since j can increment at most n times across all queries combined (as it traverses the sorted array once), the total work done by the inner while loop across all queries is O(n).
• Therefore, the overall time complexity is O(n × log n + m + n) = O(n × log n + m).

Since m (number of queries) is typically bounded by n in most practical cases, and the sorting dominates, this simplifies to O(n × log n).

Space Complexity: O(n)

• The mark array uses O(n) space to track marked indices.
• The arr array stores tuples of (value, index) for all n elements, using O(n) space.
• The ans array stores results for each query, using O(m) space, but this is typically considered output space.
• Other variables (s, j, index, k) use O(1) space.
• Total auxiliary space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Resetting the Sorted Array Pointer for Each Query

The Mistake: A common error is resetting the pointer sorted_pointer to 0 for each query, thinking we need to find the k smallest elements fresh each time:

for index_to_mark, num_smallest_to_mark in queries:
    sorted_pointer = 0  # WRONG: Resetting pointer each time
    while num_smallest_to_mark > 0 and sorted_pointer < n:
        # ... marking logic

Why It's Wrong: This would cause us to repeatedly check already-marked elements from the beginning of the sorted array, leading to:

• Incorrect results (marking wrong elements)
• Inefficient time complexity O(n*m) instead of O(n+m)

The Fix: Keep the pointer persistent across all queries. Once an element has been checked (whether marked or skipped), we never need to check it again for finding the smallest unmarked elements.

Pitfall 2: Double-Subtracting When Element Already Marked

The Mistake: Not checking if an element is already marked before subtracting from the sum:

# WRONG: Always subtract, even if already marked
total_sum -= nums[index_to_mark]
is_marked[index_to_mark] = True

Why It's Wrong: If the element at index_to_mark was already marked in a previous query (either as a specified index or as one of the k smallest), subtracting its value again would give an incorrect sum.

The Fix: Always check the marking status before updating:

if not is_marked[index_to_mark]:
    is_marked[index_to_mark] = True
    total_sum -= nums[index_to_mark]

Pitfall 3: Using the Wrong Value When Subtracting from Sum

The Mistake: When marking the k smallest elements, using the wrong value for subtraction:

# WRONG: Using the index instead of value
if not is_marked[current_index]:
    is_marked[current_index] = True
    total_sum -= current_index  # Should be current_value!

Why It's Wrong: The sorted array contains tuples of (value, original_index). We need to subtract the actual value of the element, not its index position.

The Fix: Properly destructure the tuple and use the correct component:

current_value, current_index = sorted_elements[sorted_pointer]
if not is_marked[current_index]:
    is_marked[current_index] = True
    total_sum -= current_value  # Correct: subtract the value