Mark Elements on Array by Performing Queries

Problem Description

You are given a 0-indexed array nums of size n consisting of positive integers. You are also given a 2D array queries of size m where queries[i] = [index_i, k_i]. Initially, all elements of the array are unmarked. You need to apply m queries on the array in order, where on the i-th query you do the following:

• Mark the element at index index_i if it is not already marked.
• Then mark k_i unmarked elements in the array with the smallest values. If multiple such elements exist, mark the ones with the smallest indices. And if less than k_i unmarked elements exist, then mark all of them.

Return an array answer of size m where answer[i] is the sum of unmarked elements in the array after the i-th query.

Key Insights

• The problem requires managing marked and unmarked elements efficiently.
• We need to keep track of the smallest unmarked elements while processing each query.
• Sorting or using a priority queue can help efficiently access the smallest unmarked elements.

Space and Time Complexity

Time Complexity: O(m * log(n)), where m is the number of queries and n is the size of nums. Space Complexity: O(n) for the marked/unmarked tracking.

Solution

To solve this problem, we will utilize a priority queue (min-heap) to efficiently retrieve and manage the smallest unmarked elements. The algorithm proceeds as follows:

1. Initialize a list to keep track of marked elements.
2. For each query, mark the specified index.
3. Use the min-heap to retrieve the smallest unmarked elements and mark them, respecting the count k_i.
4. After each query, compute the sum of unmarked elements and store it in the result list.

Code Solutions