#3080

Mark Elements on Array by Performing Queries

medium · 49.1% accepted · 130 likes · top 35%

array · hash table · sorting · heap (priority queue) · simulation

Description

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.

Solution