Mark Elements on Array by Performing Queries

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 sizem whereanswer[i]_is thesum of unmarked elements in the array after the _ith query.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12



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

1
2
3
4
5
6
7
8
9



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 <= 10^5
1 <= nums[i] <= 10^5
queries[i].length == 2
0 <= indexi, ki <= n - 1

Solution

Method 1 – Min-Heap and Set for Efficient Marking

Intuition

We need to efficiently mark elements by value and index, and repeatedly find the smallest unmarked elements. A min-heap (priority queue) allows us to always access the smallest unmarked value, and a set (or boolean array) tracks which indices are marked.

Approach

Initialize a min-heap with (value, index) for all elements.
Use a boolean array or set to track marked indices.
For each query:
- Mark the given index if not already marked.
- For ki times, pop the smallest (value, index) from the heap if the index is unmarked, and mark it. If not enough unmarked elements, mark all remaining.
- After marking, sum all unmarked elements and store in the answer.
Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
public:
    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<pair<int, int>> arr;
        for (int i = 0; i < n; ++i) arr.emplace_back(nums[i], i);
        sort(arr.begin(), arr.end());
        vector<bool> marked(n, false);
        long long total = 0;
        for (int x : nums) total += x;
        vector<long long> ans;
        int ptr = 0;
        for (auto& q : queries) {
            int idx = q[0], k = q[1];
            if (!marked[idx]) {
                marked[idx] = true;
                total -= nums[idx];
            }
            int cnt = 0;
            while (cnt < k && ptr < n) {
                int i = arr[ptr].second;
                if (!marked[i]) {
                    marked[i] = true;
                    total -= arr[ptr].first;
                    cnt++;
                }
                ptr++;
            }
            ans.push_back(total);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


func unmarkedSumArray(nums []int, queries [][]int) []int64 {
    n := len(nums)
    arr := make([][2]int, n)
    for i, v := range nums {
        arr[i] = [2]int{v, i}
    }
    sort.Slice(arr, func(i, j int) bool {
        if arr[i][0] == arr[j][0] {
            return arr[i][1] < arr[j][1]
        }
        return arr[i][0] < arr[j][0]
    })
    marked := make([]bool, n)
    var total int64
    for _, v := range nums {
        total += int64(v)
    }
    ans := make([]int64, 0, len(queries))
    ptr := 0
    for _, q := range queries {
        idx, k := q[0], q[1]
        if !marked[idx] {
            marked[idx] = true
            total -= int64(nums[idx])
        }
        cnt := 0
        for cnt < k && ptr < n {
            i := arr[ptr][1]
            if !marked[i] {
                marked[i] = true
                total -= int64(arr[ptr][0])
                cnt++
            }
            ptr++
        }
        ans = append(ans, total)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    public long[] unmarkedSumArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }
        Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        boolean[] marked = new boolean[n];
        long total = 0;
        for (int x : nums) total += x;
        long[] ans = new long[queries.length];
        int ptr = 0;
        for (int q = 0; q < queries.length; q++) {
            int idx = queries[q][0], k = queries[q][1];
            if (!marked[idx]) {
                marked[idx] = true;
                total -= nums[idx];
            }
            int cnt = 0;
            while (cnt < k && ptr < n) {
                int i = arr[ptr][1];
                if (!marked[i]) {
                    marked[i] = true;
                    total -= arr[ptr][0];
                    cnt++;
                }
                ptr++;
            }
            ans[q] = total;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
    fun unmarkedSumArray(nums: IntArray, queries: Array<IntArray>): LongArray {
        val n = nums.size
        val arr = Array(n) { i -> nums[i] to i }
        arr.sortWith(compareBy({ it.first }, { it.second }))
        val marked = BooleanArray(n)
        var total = nums.map { it.toLong() }.sum()
        val ans = LongArray(queries.size)
        var ptr = 0
        for ((q, query) in queries.withIndex()) {
            val (idx, k) = query
            if (!marked[idx]) {
                marked[idx] = true
                total -= nums[idx]
            }
            var cnt = 0
            while (cnt < k && ptr < n) {
                val i = arr[ptr].second
                if (!marked[i]) {
                    marked[i] = true
                    total -= arr[ptr].first
                    cnt++
                }
                ptr++
            }
            ans[q] = total
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def unmarkedSumArray(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        n = len(nums)
        arr = sorted((v, i) for i, v in enumerate(nums))
        marked = [False] * n
        total = sum(nums)
        ans = []
        ptr = 0
        for idx, k in queries:
            if not marked[idx]:
                marked[idx] = True
                total -= nums[idx]
            cnt = 0
            while cnt < k and ptr < n:
                i = arr[ptr][1]
                if not marked[i]:
                    marked[i] = True
                    total -= arr[ptr][0]
                    cnt += 1
                ptr += 1
            ans.append(total)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


impl Solution {
    pub fn unmarked_sum_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
        let n = nums.len();
        let mut arr: Vec<(i32, usize)> = nums.iter().enumerate().map(|(i, &v)| (v, i)).collect();
        arr.sort();
        let mut marked = vec![false; n];
        let mut total: i64 = nums.iter().map(|&x| x as i64).sum();
        let mut ans = Vec::with_capacity(queries.len());
        let mut ptr = 0;
        for q in &queries {
            let idx = q[0] as usize;
            let k = q[1];
            if !marked[idx] {
                marked[idx] = true;
                total -= nums[idx] as i64;
            }
            let mut cnt = 0;
            while cnt < k && ptr < n {
                let i = arr[ptr].1;
                if !marked[i] {
                    marked[i] = true;
                    total -= arr[ptr].0 as i64;
                    cnt += 1;
                }
                ptr += 1;
            }
            ans.push(total);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
    unmarkedSumArray(nums: number[], queries: number[][]): number[] {
        const n = nums.length;
        const arr = nums.map((v, i) => [v, i]).sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        const marked = Array(n).fill(false);
        let total = nums.reduce((a, b) => a + b, 0);
        const ans: number[] = [];
        let ptr = 0;
        for (const [idx, k] of queries) {
            if (!marked[idx]) {
                marked[idx] = true;
                total -= nums[idx];
            }
            let cnt = 0;
            while (cnt < k && ptr < n) {
                const i = arr[ptr][1];
                if (!marked[i]) {
                    marked[i] = true;
                    total -= arr[ptr][0];
                    cnt++;
                }
                ptr++;
            }
            ans.push(total);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O((n + m) log n), where n is the length of nums and m is the number of queries, due to sorting and iterating through queries.
🧺 Space complexity: O(n), for storing the marked array and sorted array.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Min-Heap and Set for Efficient Marking#

Intuition#

Approach#

Code#

Complexity#