Mark elements on array by performing queries

Array Hash Table Sorting Heap (Priority Queue) Simulation

49.1% acceptance

Feb 25, 2026

129

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. Mark the element at index indexi if it is not already marked. Then mark ki unmarked elements in the array with the smallest values (smallest indices to break ties). Return an array answer of size m where answer[i] is the sum of unmarked elements after the ith query.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn unmarked_sum_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
    let n = nums.len();
    let mut total: i64 = nums.iter().map(|&x| x as i64).sum();
    let mut marked = vec![false; n];
    // Sorted indices by (value, index)
    let mut sorted: Vec<usize> = (0..n).collect();
    sorted.sort_by(|&a, &b| nums[a].cmp(&nums[b]).then(a.cmp(&b)));
    let mut ptr = 0usize;
    let mut ans = vec![];
    for q in &queries {
      let idx = q[0] as usize;
      let k = q[1] as i32;
      if !marked[idx] {
        marked[idx] = true;
        total -= nums[idx] as i64;
      }
      let mut cnt = 0;
      while cnt < k && ptr < n {
        if !marked[sorted[ptr]] {
          marked[sorted[ptr]] = true;
          total -= nums[sorted[ptr]] as i64;
          cnt += 1;
        }
        ptr += 1;
      }
      ans.push(total);
    }
    ans
  }
}