Mark Elements on Array by Performing Queries

Medium
1428.

Mark Elements on Array by Performing Queries

MediumArrayHash TableSortingHeap (Priority Queue)GoogleAmazon

Mark Elements on Array by Performing Queries is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

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:

  1. Mark nums[index] if it is not marked yet.
  2. Then mark the k unmarked elements with the smallest values; among equal values, the smaller index goes first. If fewer than k elements 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.length
  • m == queries.length
  • 1 <= m <= n <= 10^5
  • 1 <= nums[i] <= 10^4
  • queries[i].length == 2
  • 0 <= index_i, k_i <= n - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var unmarkedSumArray = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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:

  1. Mark nums[index] if it is not marked yet.
  2. Then mark the k unmarked elements with the smallest values; among equal values, the smaller index goes first. If fewer than k elements 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.length
  • m == queries.length
  • 1 <= m <= n <= 10^5
  • 1 <= nums[i] <= 10^4
  • queries[i].length == 2
  • 0 <= index_i, k_i <= n - 1

Hints for Mark Elements on Array by Performing Queries

  1. Hint 1

    Keep a running total of the unmarked values and subtract each element the moment it is marked.

  2. Hint 2

    Every "smallest unmarked" request scans the elements in one fixed order: by value, then by index.

  3. 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

  1. Compute total, the sum of all values, and a boolean marked array.
  2. Sort the indices by (nums[i], i) into order; set pointer p = 0.
  3. For each query [index, k]: if index is unmarked, mark it and subtract its value.
  4. While k > 0 and p < n: take i = order[p++]; if it is unmarked, mark it, subtract its value and decrement k.
  5. Append total to 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 the k marks 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; k may 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 ans

Java

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