Watch 10 video solutions for Mark Elements on Array by Performing Queries, a medium level problem involving Array, Hash Table, Sorting. This walkthrough by Aryan Mittal has 1,198 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |