Skip to main content
Talentd

Mark Elements on Array by Performing Queries - Solution & Explanation

MediumArrayHash TableSortingHeap (Priority Queue)19 min readAsked at: Samsung, Barclays
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array nums and a list of queries [index, k]. For each query, mark the given index if it is not already marked, then mark the k smallest unmarked elements in the array. After processing the query, return the sum of all remaining unmarked elements.

The challenge is efficiently finding the smallest unmarked elements across multiple queries while avoiding repeatedly scanning the entire array. A naive simulation would be too slow for large inputs.

Approach 1: Heap and Set Approach (Min Heap) (Time: O((n + q) log n), Space: O(n))

Push every element into a min heap as (value, index). Maintain a marked structure (boolean array or set) and track the running sum of all unmarked values. For each query, first mark the requested index if it hasn't been marked and subtract its value from the running sum. Then repeatedly pop from the heap to mark the k smallest unmarked elements. If the heap top is already marked, skip it and continue popping. This works because a heap (priority queue) always gives the smallest value in O(log n) time. The running sum avoids recomputing totals after every query. This approach is straightforward and works well when queries frequently require selecting the next smallest element.

Approach 2: Sorted Index and Two-Pointer Approach (Time: O(n log n + q + n), Space: O(n))

Instead of repeatedly using a heap, pre-sort the indices of the array by their values using sorting. Maintain a pointer that walks through this sorted list to find the next smallest unmarked element. Also keep a boolean marked array to track which indices are already processed. For each query, mark the specified index if needed and subtract its value from the running sum. Then move the pointer forward, marking up to k unmarked elements from the sorted order. Skip indices already marked. Because each index is processed at most once, the pointer only moves forward, making the simulation efficient. This approach trades the heap operations for a single sort and a linear scan.

Both strategies rely on efficient bookkeeping of marked elements using structures from arrays or simple lookup tables. The key idea is avoiding repeated full scans of the array while always selecting the smallest available elements.

Recommended for interviews: The heap solution is usually the first correct optimization candidates reach because selecting the smallest element naturally suggests a priority queue. It demonstrates understanding of greedy selection with a min heap. The sorted-index approach is slightly more optimal in practice and shows deeper insight into simulation problems where elements are consumed only once.

Approach 1: Heap and Set Approach

This approach uses a heap data structure to efficiently fetch the k smallest unmarked numbers and a set to keep track of marked indices. The heap helps in order-efficient extraction of the smallest elements, and the set allows O(1) marking checks.

Explanation: The function takes the nums array and queries list as inputs. It initializes a set 'marked' to keep track of marked indices and computes initial unmarked_sum. Using a min-heap, all elements with their indices are stored to facilitate the smallest element extraction. For each query, it marks the specified index and k smallest unmarked elements, updating the unmarked_sum accordingly.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n + m log n), due to heap operations for m queries.
Space Complexity: O(n), for storing indices in heap and set.
Try this approach in the editor →

Approach 2: Sorted Index and Two-Pointer Approach

This approach sorts the indices of the array based on their values and uses a two-pointer strategy to efficiently mark elements. By pre-sorting, we can make an optimal sequence of marking decisions via two-pointer traversal while maintaining marked updates in a set.

Explanation: The JavaScript version sorts the array indices based on values, allowing efficient marking via two-pointer traversal through sorted indices. A set tracks marked indices, and unmarked_sum is dynamically updated during each query execution.

Code

JavaScriptC#C

JavaScript

C#

C

Complexity

Time Complexity: O(n log n + m * n), as sorting is followed by iteration.
Space Complexity: O(n), for storing sorted pairs.
Try this approach in the editor →

Approach 3: Sorting + Simulation

First, we calculate the sum s of the array nums. We define an array mark to indicate whether the elements in the array have been marked, initializing all elements as unmarked.

Then, we create an array arr, where each element is a tuple (x, i), indicating that the i-th element in the array has a value of x. We sort the array arr by the value of the elements. If the values are equal, we sort them in ascending order of the index.

Next, we traverse the array queries. For each query [index, k], we first check whether the element at index index has been marked. If it has not been marked, we mark it and subtract the value of the element at index index from s. Then, we traverse the array arr. For each element (x, i), if element i has not been marked, we mark it and subtract the value x corresponding to element i from s, until k is 0 or the array arr is fully traversed. Then, we add s to the answer array.

After traversing all the queries, we get the answer array.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Heap and Set ApproachTime Complexity: O(n + m log n), due to heap operations for m queries.
Space Complexity: O(n), for storing indices in heap and set.
Sorted Index and Two-Pointer ApproachTime Complexity: O(n log n + m * n), as sorting is followed by iteration.
Space Complexity: O(n), for storing sorted pairs.
Sorting + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Heap and Set (Min Heap)O((n + q) log n)O(n)General case. Easy to implement when repeatedly selecting the smallest remaining element.
Sorted Index + Two PointerO(n log n + n + q)O(n)Better when elements are consumed once. Replaces heap operations with a single sort and linear scan.

Video Solution

3080. Mark Elements on Array by Performing Queries | Set | Min Heap | Priority Queue • Aryan Mittal • 1,223 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Mark Elements on Array by Performing Queries easy or hard?
The problem is rated Medium because the core logic is simple but requires careful handling of repeated queries and efficient smallest-element selection. Recognizing that a min heap or sorted order can avoid repeated scans is the key insight.
How to solve Mark Elements on Array by Performing Queries in O(n log n)?
Pre-sort array indices by their values and maintain a pointer to the smallest unmarked element. Track marked indices with a boolean array and maintain a running sum of unmarked elements. Each index is marked at most once, so after the initial O(n log n) sorting step the rest of the queries run in linear time overall.
What is the best approach for Mark Elements on Array by Performing Queries?
Two efficient approaches exist: a min heap simulation and a sorted index pointer method. The heap approach keeps all elements in a priority queue and repeatedly extracts the smallest unmarked value in O(log n). The sorted index approach sorts indices by value once and then uses a pointer to mark elements only once, which can be slightly faster in practice.
Is Mark Elements on Array by Performing Queries asked at Google/Amazon/Meta?
Problems combining heaps, greedy selection, and query simulation appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests your ability to combine a priority queue with efficient bookkeeping of processed elements.
What data structure is used in Mark Elements on Array by Performing Queries?
The primary data structure is a min heap (priority queue) that always returns the smallest array value. A boolean array or set tracks which indices are already marked. Some optimized solutions also rely on sorted arrays and two-pointer scanning.
What is the time complexity of Mark Elements on Array by Performing Queries?
The heap-based solution runs in O((n + q) log n) time because each heap operation costs O(log n). The sorted index solution runs in O(n log n + q + n), dominated by the initial sort. Both approaches use O(n) additional space for tracking marked indices.
Mark Elements on Array by Performing Queries Python or Java solution approach?
In Python or Java, push all elements into a priority queue as (value, index). Maintain a marked array and a running sum of remaining values. For each query, mark the requested index and then pop the k smallest unmarked elements from the heap, updating the sum accordingly.

Ready to solve this problem?

Practice Mark Elements on Array by Performing Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays