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] = [indexi, ki].
Initially all elements of the array are unmarked.
You need to apply m queries on the array in order, where on the ith query you do the following:
indexi if it is not already marked.ki 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 ki 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 ith query.
Example 1:
Input: nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]
Output: [8,3,0]
Explanation:
We do the following queries on the array:
1, and 2 of the smallest unmarked elements with the smallest indices if they exist, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 2 + 2 + 3 + 1 = 8.3, since it is already marked we skip it. Then we mark 3 of the smallest unmarked elements with the smallest indices, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 3.4, since it is already marked we skip it. Then we mark 2 of the smallest unmarked elements with the smallest indices if they exist, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 0.Example 2:
Input: nums = [1,4,2,3], queries = [[0,1]]
Output: [7]
Explanation: We do one query which is mark the element at index 0 and mark the smallest element among unmarked elements. The marked elements will be nums = [1,4,2,3], and the sum of unmarked elements is 4 + 3 = 7.
Constraints:
n == nums.lengthm == queries.length1 <= m <= n <= 1051 <= nums[i] <= 105queries[i].length == 20 <= indexi, ki <= n - 1Problem Overview: You are given an array nums and a list of queries [index, k]. For each query, mark the given index if it is not already marked, then mark the k smallest unmarked elements in the array. After processing the query, return the sum of all remaining unmarked elements.
The challenge is efficiently finding the smallest unmarked elements across multiple queries while avoiding repeatedly scanning the entire array. A naive simulation would be too slow for large inputs.
Approach 1: Heap and Set Approach (Min Heap) (Time: O((n + q) log n), Space: O(n))
Push every element into a min heap as (value, index). Maintain a marked structure (boolean array or set) and track the running sum of all unmarked values. For each query, first mark the requested index if it hasn't been marked and subtract its value from the running sum. Then repeatedly pop from the heap to mark the k smallest unmarked elements. If the heap top is already marked, skip it and continue popping. This works because a heap (priority queue) always gives the smallest value in O(log n) time. The running sum avoids recomputing totals after every query. This approach is straightforward and works well when queries frequently require selecting the next smallest element.
Approach 2: Sorted Index and Two-Pointer Approach (Time: O(n log n + q + n), Space: O(n))
Instead of repeatedly using a heap, pre-sort the indices of the array by their values using sorting. Maintain a pointer that walks through this sorted list to find the next smallest unmarked element. Also keep a boolean marked array to track which indices are already processed. For each query, mark the specified index if needed and subtract its value from the running sum. Then move the pointer forward, marking up to k unmarked elements from the sorted order. Skip indices already marked. Because each index is processed at most once, the pointer only moves forward, making the simulation efficient. This approach trades the heap operations for a single sort and a linear scan.
Both strategies rely on efficient bookkeeping of marked elements using structures from arrays or simple lookup tables. The key idea is avoiding repeated full scans of the array while always selecting the smallest available elements.
Recommended for interviews: The heap solution is usually the first correct optimization candidates reach because selecting the smallest element naturally suggests a priority queue. It demonstrates understanding of greedy selection with a min heap. The sorted-index approach is slightly more optimal in practice and shows deeper insight into simulation problems where elements are consumed only once.
This approach uses a heap data structure to efficiently fetch the k smallest unmarked numbers and a set to keep track of marked indices. The heap helps in order-efficient extraction of the smallest elements, and the set allows O(1) marking checks.
Explanation: The function takes the nums array and queries list as inputs. It initializes a set 'marked' to keep track of marked indices and computes initial unmarked_sum. Using a min-heap, all elements with their indices are stored to facilitate the smallest element extraction. For each query, it marks the specified index and k smallest unmarked elements, updating the unmarked_sum accordingly.
This approach sorts the indices of the array based on their values and uses a two-pointer strategy to efficiently mark elements. By pre-sorting, we can make an optimal sequence of marking decisions via two-pointer traversal while maintaining marked updates in a set.
Explanation: The JavaScript version sorts the array indices based on values, allowing efficient marking via two-pointer traversal through sorted indices. A set tracks marked indices, and unmarked_sum is dynamically updated during each query execution.
JavaScript
C#
C
First, we calculate the sum s of the array nums. We define an array mark to indicate whether the elements in the array have been marked, initializing all elements as unmarked.
Then, we create an array arr, where each element is a tuple (x, i), indicating that the i-th element in the array has a value of x. We sort the array arr by the value of the elements. If the values are equal, we sort them in ascending order of the index.
Next, we traverse the array queries. For each query [index, k], we first check whether the element at index index has been marked. If it has not been marked, we mark it and subtract the value of the element at index index from s. Then, we traverse the array arr. For each element (x, i), if element i has not been marked, we mark it and subtract the value x corresponding to element i from s, until k is 0 or the array arr is fully traversed. Then, we add s to the answer array.
After traversing all the queries, we get the answer array.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Heap and Set Approach | Time Complexity: O(n + m log n), due to heap operations for m queries. Space Complexity: O(n), for storing indices in heap and set. |
| Sorted Index and Two-Pointer Approach | Time Complexity: O(n log n + m * n), as sorting is followed by iteration. Space Complexity: O(n), for storing sorted pairs. |
| Sorting + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Heap and Set (Min Heap) | O((n + q) log n) | O(n) | General case. Easy to implement when repeatedly selecting the smallest remaining element. |
| Sorted Index + Two Pointer | O(n log n + n + q) | O(n) | Better when elements are consumed once. Replaces heap operations with a single sort and linear scan. |
3080. Mark Elements on Array by Performing Queries | Set | Min Heap | Priority Queue • Aryan Mittal • 1,198 views views
Watch 9 more video solutions →Practice Mark Elements on Array by Performing Queries with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor