# Mark Elements on Array by Performing Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/mark-elements-on-array-by-performing-queries)
Canonical: https://scaleengineer.com/dsa/problems/mark-elements-on-array-by-performing-queries
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays), [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
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:

* Mark the element at index `indexi` if it is not already marked.
* Then mark `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:

* Mark the element at index `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`.
* Mark the element at index `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`.
* Mark the element at index `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.length`
* `m == queries.length`
* `1 <= m <= n <= 105`
* `1 <= nums[i] <= 105`
* `queries[i].length == 2`
* `0 <= indexi, ki <= n - 1`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. For each query, it first marks the specified index. Then, to find the `k` smallest unmarked elements, it gathers all currently unmarked elements into a temporary list, sorts this list based on value and then index, and marks the top `k` elements from the sorted list. The sum of unmarked elements is updated at each step.
**Time:** O(m * n log n). For each of the `m` queries, we scan the `n` elements to find unmarked ones (O(n)) and then sort them (O(n log n)). This makes the total time complexity dominated by the sorting step within the loop. · **Space:** O(n + m). We need O(n) space for the `marked` array and the temporary list of unmarked elements. The answer array requires O(m) space.
**Pros:** Simple to understand and follows the problem statement directly.
**Cons:** Extremely inefficient due to repeated scanning and sorting of the array.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
We maintain a boolean array `marked` to keep track of marked elements and a variable `totalSum` for the sum of unmarked elements. Initially, `marked` is all `false`, and `totalSum` is the total sum of `nums`. For each query `[index, k]`, we first handle marking by index. If `marked[index]` is false, we set it to true and update `totalSum`. Then, for marking by value, we build a list of all unmarked elements with their values and original indices. This list is sorted to find the smallest elements. We then iterate through the top `k` elements of this sorted list, mark them, and update `totalSum`. Finally, the updated `totalSum` is recorded as the answer for the current query.

```java
class Solution {
    public long[] unmarkedSumArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int m = queries.length;
        long[] ans = new long[m];
        boolean[] marked = new boolean[n];
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        for (int i = 0; i < m; i++) {
            int index = queries[i][0];
            int k = queries[i][1];

            // Mark by index
            if (!marked[index]) {
                marked[index] = true;
                totalSum -= nums[index];
            }

            // Mark k smallest unmarked elements
            List<int[]> unmarkedElements = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (!marked[j]) {
                    unmarkedElements.add(new int[]{nums[j], j});
                }
            }

            unmarkedElements.sort((a, b) -> {
                if (a[0] != b[0]) {
                    return Integer.compare(a[0], b[0]);
                } else {
                    return Integer.compare(a[1], b[1]);
                }
            });

            int count = 0;
            for (int[] element : unmarkedElements) {
                if (count >= k) break;
                int val = element[0];
                int idx = element[1];
                if (!marked[idx]) {
                    marked[idx] = true;
                    totalSum -= val;
                    count++;
                }
            }
            ans[i] = totalSum;
        }

        return ans;
    }
}
```
### Algorithm
- Initialize a boolean array `marked` of size `n` to keep track of marked elements, initially all `false`.
- Calculate the initial sum of all elements in `nums` and store it in `totalSum`.
- For each query `[index, k]`:
  1. Check if `nums[index]` is already marked. If not, mark it by setting `marked[index] = true` and subtract `nums[index]` from `totalSum`.
  2. To find the `k` smallest unmarked elements, create a temporary list of pairs `(value, original_index)` for all elements where `marked[original_index]` is `false`.
  3. Sort this temporary list. The primary sorting key is the value, and the secondary key is the index.
  4. Iterate through the first `k` elements of the sorted list (or fewer if the list is smaller than `k`).
  5. For each of these elements, mark its original index in the `marked` array and subtract its value from `totalSum`.
  6. After processing both marking steps, add the current `totalSum` to the answer array.
- Return the answer array.

## Optimized Selection with a Min-Heap
This approach significantly optimizes the process of finding the `k` smallest unmarked elements. Instead of repeatedly sorting a list, we use a min-heap (Priority Queue in Java) to maintain all elements in a sorted manner throughout the process. This allows for efficient retrieval of the smallest unmarked elements.
**Time:** O((n+m) log n) or more tightly O(n log n + m). Building the heap takes O(n log n). Each of the `n` elements is extracted from the heap at most once across all `m` queries. The total time for all heap extractions is O(n log n). The main loop runs `m` times. · **Space:** O(n + m). The min-heap stores `n` elements, the `marked` array takes O(n) space, and the answer array takes O(m) space.
**Pros:** Much more efficient than the brute-force approach.; A standard and robust solution for problems requiring repeated extraction of minimum/maximum elements.
**Cons:** While efficient, the O(n log n) complexity might be suboptimal if the range of values in `nums` is small, where a linear time solution could exist.
### Explanation
We start by populating a min-heap with all elements of `nums`, storing them as `(value, index)` pairs. The heap's comparator ensures that elements with smaller values, or smaller indices in case of a tie, have higher priority. We also maintain a `marked` boolean array and a `totalSum` of unmarked elements. For each query, we first mark the element at the given index and update the sum. Then, we extract elements from the heap `k` times. A crucial step is to check if an element extracted from the heap is already marked. If it is, we ignore it and proceed to the next, as it must have been marked by its index in a prior operation. If not marked, we mark it, update the sum, and continue until `k` new elements are marked or the heap is empty.

```java
class Solution {
    public long[] unmarkedSumArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int m = queries.length;
        long[] ans = new long[m];
        boolean[] marked = new boolean[n];
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            } else {
                return Integer.compare(a[1], b[1]);
            }
        });

        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
        }

        for (int i = 0; i < m; i++) {
            int index = queries[i][0];
            int k = queries[i][1];

            // Mark by index
            if (!marked[index]) {
                marked[index] = true;
                totalSum -= nums[index];
            }

            // Mark k smallest unmarked elements
            int count = 0;
            while (count < k && !pq.isEmpty()) {
                int[] top = pq.poll();
                int val = top[0];
                int idx = top[1];

                if (!marked[idx]) {
                    marked[idx] = true;
                    totalSum -= val;
                    count++;
                }
            }
            ans[i] = totalSum;
        }

        return ans;
    }
}
```
### Algorithm
- Initialize a `marked` boolean array and calculate the `totalSum` as before.
- Create a min-heap (Priority Queue) and insert all elements from `nums` as pairs of `(value, index)`.
- The heap should be ordered by value first, then by index for tie-breaking.
- For each query `[index, k]`:
  1. Mark by index: If `!marked[index]`, set `marked[index] = true` and `totalSum -= nums[index]`.
  2. Mark by value: Initialize a counter `markedCount = 0`.
  3. While `markedCount < k` and the heap is not empty, extract the minimum element `(val, idx)` from the heap.
  4. If `marked[idx]` is `true`, it means this element was already marked (e.g., by index in a previous step), so we discard it and continue.
  5. If `!marked[idx]`, we mark it (`marked[idx] = true`), subtract its value from `totalSum`, and increment `markedCount`.
  6. Store the final `totalSum` for the query.
- Return the answer array.

## Linear Time Solution with Value Grouping
This is the most efficient approach, achieving linear time complexity by leveraging the constraint on the range of values in `nums`. It avoids general-purpose sorting by grouping elements by their value, similar to a counting sort. This allows finding the smallest unmarked elements by simply iterating through values in increasing order.
**Time:** O(n + m + W), where `W` is the maximum value in `nums`. O(n) for pre-processing. The query processing takes O(m + n + W) in total because each pointer (`valuePointer` and `indexPointers`) only moves forward, traversing each element and value at most once across all queries. · **Space:** O(n + m + W), where `W` is the maximum possible value in `nums`. O(n) for the `marked` array and storing all indices, O(W) for `valueToIndices` and `indexPointers` arrays, and O(m) for the answer.
**Pros:** Optimal time complexity, linear in the input size and value range.; Very fast for the given constraints.
**Cons:** Slightly more complex to implement due to the need to manage multiple pointers.; Uses more memory if the maximum value `W` is very large, though it's fine for the given constraints.
### Explanation
The core idea is to pre-process the array to group indices by value. We can use an array of lists, say `valueToIndices`, where the index of the array corresponds to a value from `nums`, and the list at that index stores all original indices where this value appears. By populating this structure by iterating through `nums` from left to right, the lists of indices will be naturally sorted. We then use pointers to traverse this structure efficiently. A `valuePointer` keeps track of the smallest value we need to consider, and an `indexPointer` for each value's list tracks how many of its occurrences we've already marked. During a query, to mark `k` elements, we use these pointers to find the next available unmarked elements in O(1) amortized time, starting from the smallest values and respecting the smallest index rule.

```java
class Solution {
    public long[] unmarkedSumArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int m = queries.length;
        long[] ans = new long[m];
        boolean[] marked = new boolean[n];
        long totalSum = 0;

        List<Integer>[] valueToIndices = new List[100001];
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
            if (valueToIndices[nums[i]] == null) {
                valueToIndices[nums[i]] = new ArrayList<>();
            }
            valueToIndices[nums[i]].add(i);
        }

        int[] indexPointers = new int[100001];
        int valuePointer = 1;

        for (int i = 0; i < m; i++) {
            int index = queries[i][0];
            int k = queries[i][1];

            // Mark by index
            if (!marked[index]) {
                marked[index] = true;
                totalSum -= nums[index];
            }

            // Mark k smallest unmarked elements
            int count = 0;
            while (count < k && valuePointer < valueToIndices.length) {
                List<Integer> indices = valueToIndices[valuePointer];
                if (indices == null || indexPointers[valuePointer] >= indices.size()) {
                    valuePointer++;
                    continue;
                }

                int originalIndex = indices.get(indexPointers[valuePointer]);
                if (!marked[originalIndex]) {
                    marked[originalIndex] = true;
                    totalSum -= valuePointer;
                    count++;
                }
                indexPointers[valuePointer]++;
            }
            ans[i] = totalSum;
        }

        return ans;
    }
}
```
### Algorithm
- Initialize a `marked` boolean array and `totalSum`.
- Pre-process `nums` by grouping indices by their value. Use an array of lists, `valueToIndices`, where `valueToIndices[v]` contains a sorted list of indices `i` where `nums[i] == v`.
- Maintain a `valuePointer` to track the smallest value we are currently considering, and an array of `indexPointers` to track the next available index for each value's list.
- For each query `[index, k]`:
  1. Mark by index as usual, updating `marked` and `totalSum`.
  2. Mark by value: Start from the current `valuePointer`. Iterate through the list of indices for this value, starting from its `indexPointer`.
  3. For each index, if it's not marked, mark it, update `totalSum`, and increment a counter for the `k` elements.
  4. If the list for the current value is exhausted, increment `valuePointer` to move to the next smallest value.
  5. Continue until `k` elements are marked or all elements are processed.
  6. Store the `totalSum`.
- Return the answer array.

# Solutions
### Java

```java
class Solution {
public
  long[] unmarkedSumArray(int[] nums, int[][] queries) {
    int n = nums.length;
    long s = Arrays.stream(nums).asLongStream().sum();
    boolean[] mark = new boolean[n];
    int[][] arr = new int[n][0];
    for (int i = 0; i < n; ++i) {
      arr[i] = new int[]{nums[i], i};
    }
    Arrays.sort(arr, (a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    int m = queries.length;
    long[] ans = new long[m];
    for (int i = 0, j = 0; i < m; ++i) {
      int index = queries[i][0], k = queries[i][1];
      if (!mark[index]) {
        mark[index] = true;
        s -= nums[index];
      }
      for (; k > 0 && j < n; ++j) {
        if (!mark[arr[j][1]]) {
          mark[arr[j][1]] = true;
          s -= arr[j][0];
          --k;
        }
      }
      ans[i] = s;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<long long> unmarkedSumArray(vector<int> &nums,
                                     vector<vector<int>> &queries) {
    int n = nums.size();
    long long s = accumulate(nums.begin(), nums.end(), 0LL);
    vector<bool> mark(n);
    vector<pair<int, int>> arr;
    for (int i = 0; i < n; ++i) {
      arr.emplace_back(nums[i], i);
    }
    sort(arr.begin(), arr.end());
    vector<long long> ans;
    int m = queries.size();
    for (int i = 0, j = 0; i < m; ++i) {
      int index = queries[i][0], k = queries[i][1];
      if (!mark[index]) {
        mark[index] = true;
        s -= nums[index];
      }
      for (; k && j < n; ++j) {
        if (!mark[arr[j].second]) {
          mark[arr[j].second] = true;
          s -= arr[j].first;
          --k;
        }
      }
      ans.push_back(s);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]: n = len(nums) s = sum(nums) mark = [False] * n arr = sorted((x, i) for i, x in enumerate(nums)) j = 0 ans = [] for index, k in queries: if not mark[index]: mark[index] = True s -= nums[index] while k and j < n: if not mark[arr[j][1]]: mark[arr[j][1]] = True s -= arr[j][0] k -= 1 j += 1 ans . append(s) return ans

```