Mark Elements on Array by Performing Queries — Solution
Mark Elements on Array by Performing Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Mark Elements on Array by Performing Queries is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of n positive integers, all initially unmarked, and m queries where queries[i] = [index, k]. Apply the queries in order. Query i does two things:
- Mark
nums[index]if it is not marked yet. - Then mark the
kunmarked elements with the smallest values; among equal values, the smaller index goes first. If fewer thankelements are unmarked, mark all of them.
Return an array answer of length m where answer[i] is the sum of the unmarked elements right after query i.
Constraint note: values are capped at 10^4 (the original allows 10^5) so every sum fits in a 32-bit integer.
Example 1
Input: nums = [4,1,3,1,5], queries = [[2,1],[0,2],[4,0]]
Output: [10,0,0]
Explanation: Query 1 marks index 2 (3) and then the smallest value, the 1 at index 1: unmarked 4+1+5 = 10. Query 2 marks index 0 and then the 1 at index 3 and the 5: nothing is left.
Example 2
Input: nums = [2,7,2], queries = [[1,1]]
Output: [2]
Explanation: Index 1 (7) is marked, then the 2 at index 0 (the lower index wins the tie).
Constraints
n == nums.lengthm == queries.length1 <= m <= n <= 10^51 <= nums[i] <= 10^4queries[i].length == 20 <= index_i, k_i <= n - 1
Hints for Mark Elements on Array by Performing Queries
Hint 1
Keep a running total of the unmarked values and subtract each element the moment it is marked.
Hint 2
Every "smallest unmarked" request scans the elements in one fixed order: by value, then by index.
Hint 3
Sort the indices once by
(value, index)and keep a pointer into that order that only moves forward, skipping anything already marked.
How to solve Mark Elements on Array by Performing Queries
The order in which step 2 consumes elements never changes — ascending value, ties by index — so precompute it once (sorting, or a min-heap of (value, index)) and walk it with a single pointer, skipping elements that query step 1 already marked.
Approach
- Compute
total, the sum of all values, and a booleanmarkedarray. - Sort the indices by
(nums[i], i)intoorder; set pointerp = 0. - For each query
[index, k]: ifindexis unmarked, mark it and subtract its value. - While
k > 0andp < n: takei = order[p++]; if it is unmarked, mark it, subtract its value and decrementk. - Append
totalto the answer.
Why it works
Step 2 always wants the first unmarked element of order. Everything before p is marked (either the pointer marked it or it was skipped because it already was), so the first unmarked element is at or after p — the pointer never has to move back. Each index is passed by the pointer once, so all queries together cost O(n) after the sort.
Complexity
- Time —
O(n log n + m) - Space —
O(n)
Pitfalls
- An element marked by step 1 may still appear later in
order; skip it without spending one of thekmarks on it. - Ties must go to the smaller index — sort by the pair, not by value alone.
- The answer can drop to 0 and stay there;
kmay be 0, in which case only step 1 happens.
Reference solution
Python
from typing import List
def unmarkedSumArray(nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
order = sorted(range(n), key=lambda i: (nums[i], i))
marked = [False] * n
total = sum(nums)
p = 0
ans = []
for index, k in queries:
if not marked[index]:
marked[index] = True
total -= nums[index]
while k > 0 and p < n:
i = order[p]
p += 1
if not marked[i]:
marked[i] = True
total -= nums[i]
k -= 1
ans.append(total)
return ansJava
public static int[] unmarkedSumArray(int[] nums, int[][] queries) {
int n = nums.length;
Integer[] order = new Integer[n];
int total = 0;
for (int i = 0; i < n; i++) {
order[i] = i;
total += nums[i];
}
Arrays.sort(order, (a, b) -> nums[a] != nums[b] ? Integer.compare(nums[a], nums[b]) : Integer.compare(a, b));
boolean[] marked = new boolean[n];
int p = 0;
int[] ans = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int index = queries[q][0], k = queries[q][1];
if (!marked[index]) {
marked[index] = true;
total -= nums[index];
}
while (k > 0 && p < n) {
int j = order[p++];
if (!marked[j]) {
marked[j] = true;
total -= nums[j];
k--;
}
}
ans[q] = total;
}
return ans;
}C++
vector<int> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> order(n);
long long total = 0;
for (int i = 0; i < n; i++) {
order[i] = i;
total += nums[i];
}
sort(order.begin(), order.end(), [&](int a, int b) {
return nums[a] != nums[b] ? nums[a] < nums[b] : a < b;
});
vector<bool> marked(n, false);
int p = 0;
vector<int> ans;
for (auto& qu : queries) {
int index = qu[0], k = qu[1];
if (!marked[index]) {
marked[index] = true;
total -= nums[index];
}
while (k > 0 && p < n) {
int j = order[p++];
if (!marked[j]) {
marked[j] = true;
total -= nums[j];
k--;
}
}
ans.push_back((int) total);
}
return ans;
}JavaScript
var unmarkedSumArray = function(nums, queries) {
var n = nums.length;
var order = [];
var marked = [];
var total = 0;
for (var i = 0; i < n; i++) {
order.push(i);
marked.push(false);
total += nums[i];
}
order.sort(function(a, b) { return nums[a] - nums[b] || a - b; });
var p = 0;
var ans = [];
for (var q = 0; q < queries.length; q++) {
var index = queries[q][0], k = queries[q][1];
if (!marked[index]) {
marked[index] = true;
total -= nums[index];
}
while (k > 0 && p < n) {
var j = order[p++];
if (!marked[j]) {
marked[j] = true;
total -= nums[j];
k--;
}
}
ans.push(total);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets