Mark Elements on Array by Performing Queries

Mark Elements on Array by Performing Queries

What is this problem about?

In this problem, you are given an array of integers and a series of queries. Each query consists of two parts: an index and a count k. For each query, you must first "mark" the element at the given index (if it isn't already marked). Then, you must find the k strictly smallest unmarked elements in the entire array and mark them. After each query, you must return the sum of all elements that are currently unmarked.

Why is this asked in interviews?

This problem is a fantastic test of data structure orchestration. Interviewers use it to see if a candidate can handle operations that require two completely different lookup methods simultaneously: accessing elements by their original index, and accessing elements by their sorted value. It heavily tests your comfort with Priority Queues (Heaps) and state synchronization.

Algorithmic pattern used

This problem requires a Min Heap (Priority Queue) and an Array/Hash Set for tracking marked states.

1. Calculate the initial total sum of the array.
2. Push all elements into a Min Heap as tuples: (value, original_index). The heap orders primarily by value, and secondarily by index.
3. Maintain a boolean array marked of size N.
4. For each query [index, k]:
   • If marked[index] is false, mark it, and subtract its value from the total sum.
   • Pop from the Min Heap. If the popped element's index is already marked, discard it and pop again.
   • When you find a valid unmarked element, mark it, subtract from the sum, and decrement k. Repeat until k is 0 or the heap is empty.
   • Return the current total sum.

Example explanation

Array: [1, 2, 2, 1]. Total Sum = 6. Heap: (1, idx 0), (1, idx 3), (2, idx 1), (2, idx 2). Query 1: [1, 2] (Mark index 1, then mark 2 smallest).

• Mark index 1 (value 2). Sum becomes 6 - 2 = 4.
• Need 2 smallest.
  • Pop (1, idx 0). Unmarked! Mark it. Sum becomes 4 - 1 = 3. k becomes 1.
  • Pop (1, idx 3). Unmarked! Mark it. Sum becomes 3 - 1 = 2. k becomes 0.
• Query 1 returns 2. Query 2: [3, 1] (Mark index 3, then 1 smallest).
• Mark index 3. Wait, it's already marked! Sum remains 2.
• Need 1 smallest.
  • Pop (2, idx 1). Wait, index 1 is already marked! Discard.
  • Pop (2, idx 2). Unmarked! Mark it. Sum becomes 2 - 2 = 0.
• Query 2 returns 0.

Common mistakes candidates make

A major pitfall is trying to search the array linearly for the k smallest elements, which results in $O(N \times Q)$ time complexity and a Time Limit Exceeded error. Another common mistake is trying to physically delete elements from the array or update the heap when a specific index is marked. Deleting specific elements from a heap is $O(N)$. Instead, use "Lazy Deletion" by popping and ignoring elements that the marked array flags as obsolete.

Interview preparation tip

For this interview pattern, deeply understand "Lazy Deletion" in Priority Queues. When an item changes state (like being marked via direct index access), don't waste time hunting for it in the heap. Just let it sit there. The next time the heap pops it up naturally, check your boolean marked array. If it's stale, toss it and pop the next one. This guarantees $O(\log N)$ performance.