Mark Elements on Array by Performing Queries solution and explanation
8 more videos on this problem
3080. Mark Elements on Array by Performing Queries | Set | Min Heap | Priority QueueAryan Mittal · 16:22 · 1K views
100209. Mark Elements on Array by Performing Queries | Leetcode | Biweekly Contest 126 | Sol Code .Optimization · 0:23 · 599 views
3080. Mark Elements on Array by Performing Queries (Leetcode Medium)Programming Live with Larry · 7:51 · 230 views
3080. Mark Elements on Array by Performing Queries | Biweekly 126 | Min Heap | Implementation | C++Priyanshi Porwal · 22:12 · 215 views
Leetcode 3080: Mark Elements on Array by Performing QueriesAlgorithms Casts · 14:51 · 213 views
Leetcode 3080. Mark Elements on Array by Performing QueriesElite Code · 38:05 · 136 views
LeetCode | 3080. Mark Elements on Array by Performing Queries | Medium | Biweekly Contest 126Coding with Bobby · 11:29 · 112 views
Biweekly Contest 126 | Mark Elements on Array by Performing QueriesCodeWithMe21 · 5:25 · 103 views
✂️Biweekly Contest 126 is Here ! Problem 2: 3080. Mark Elements on Array by Performing QueriesAchyuth Chowdary · 13:38 · 32 views
The 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
indexiif it is not already marked. - Then mark
kiunmarked elements in the array with the smallest values. If multiple such elements exist, mark the ones with the smallest indices. And if less thankiunmarked 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, and2of the smallest unmarked elements with the smallest indices if they exist, the marked elements now arenums = [1,2,2,1,2,3,1]. The sum of unmarked elements is2 + 2 + 3 + 1 = 8. - Mark the element at index
3, since it is already marked we skip it. Then we mark3of the smallest unmarked elements with the smallest indices, the marked elements now arenums = [1,2,2,1,2,3,1]. The sum of unmarked elements is3. - Mark the element at index
4, since it is already marked we skip it. Then we mark2of the smallest unmarked elements with the smallest indices if they exist, the marked elements now arenums = [1,2,2,1,2,3,1]. The sum of unmarked elements is0.
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.lengthm == queries.length1 <= m <= n <= 1051 <= nums[i] <= 105queries[i].length == 20 <= 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.
import heapq
def mark_elements(nums, queries):
n = len(nums)
marked = set()
unmarked_sum = sum(nums)
# Unmarked elements as (value, index)
min_heap = [(nums[i], i) for i in range(n)]
heapq.heapify(min_heap)
result = []
for index, k in queries:
if index not in marked:
marked.add(index)
unmarked_sum -= nums[index]
# Mark k smallest unmarked elements
count = 0
while min_heap and count < k:
value, i = heapq.heappop(min_heap)
if i not in marked:
marked.add(i)
unmarked_sum -= value
count += 1
result.append(unmarked_sum)
return result
# Example usage:
nums = [1, 2, 2, 1, 2, 3, 1]
queries = [[1, 2], [3, 3], [4, 2]]
print(mark_elements(nums, queries)) # Output: [8, 3, 0]import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;
public class MarkElements {
public int[] markElements(int[] nums, int[][] queries) {
int n = nums.length;
Set<Integer> marked = new HashSet<>();
int unmarkedSum = 0;
for (int num : nums) unmarkedSum += num;
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < n; i++) minHeap.add(new int[]{nums[i], i});
int[] result = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int index = queries[q][0];
int k = queries[q][1];
if (!marked.contains(index)) {
marked.add(index);
unmarkedSum -= nums[index];
}
int count = 0;
while (!minHeap.isEmpty() && count < k) {
int[] entry = minHeap.poll();
int value = entry[0];
int i = entry[1];
if (!marked.contains(i)) {
marked.add(i);
unmarkedSum -= value;
count++;
}
}
result[q] = unmarkedSum;
}
return result;
}
// Example usage
public static void main(String[] args) {
MarkElements solution = new MarkElements();
int[] nums = {1, 2, 2, 1, 2, 3, 1};
int[][] queries = {{1, 2}, {3, 3}, {4, 2}};
int[] result = solution.markElements(nums, queries);
for (int res : result) {
System.out.println(res);
}
}
}#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
vector<int> markElements(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
unordered_set<int> marked;
int unmarkedSum = accumulate(nums.begin(), nums.end(), 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
for (int i = 0; i < n; ++i) {
minHeap.push({nums[i], i});
}
vector<int> result;
for (auto& query : queries) {
int index = query[0];
int k = query[1];
if (marked.find(index) == marked.end()) {
marked.insert(index);
unmarkedSum -= nums[index];
}
int count = 0;
while (!minHeap.empty() && count < k) {
auto [value, i] = minHeap.top();
minHeap.pop();
if (marked.find(i) == marked.end()) {
marked.insert(i);
unmarkedSum -= value;
++count;
}
}
result.push_back(unmarkedSum);
}
return result;
}
int main() {
vector<int> nums = {1, 2, 2, 1, 2, 3, 1};
vector<vector<int>> queries = {{1, 2}, {3, 3}, {4, 2}};
vector<int> result = markElements(nums, queries);
for (int res : result) {
cout << res << " ";
}
return 0;
}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.
Space Complexity: O(n), for storing indices in heap and set.
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.
function markElements(nums, queries) {
let n = nums.length;
let marked = new Set();
let unmarkedSum = nums.reduce((a, b) => a + b, 0);
// Create a list of tuples [(value, index)]
let sortedIndices = nums.map((value, i) => ({value, index: i}));
sortedIndices.sort((a, b) => a.value - b.value || a.index - b.index);
let result = [];
for (let [index, k] of queries) {
if (!marked.has(index)) {
marked.add(index);
unmarkedSum -= nums[index];
}
let count = 0;
for (let {value, index: i} of sortedIndices) {
if (count >= k) break;
if (!marked.has(i)) {
marked.add(i);
unmarkedSum -= value;
count += 1;
}
}
result.push(unmarkedSum);
}
return result;
}
// Example usage:
let nums = [1, 2, 2, 1, 2, 3, 1];
let queries = [[1, 2], [3, 3], [4, 2]];
console.log(markElements(nums, queries)); // Output: [8, 3, 0]#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int value;
int index;
} Element;
int compareElements(const void* a, const void* b) {
Element* elem1 = (Element*)a;
Element* elem2 = (Element*)b;
if (elem1->value == elem2->value) {
return elem1->index - elem2->index;
}
return elem1->value - elem2->value;
}
int* markElements(int* nums, int numsSize, int** queries, int queriesSize, int* resultSize) {
bool* marked = (bool*)calloc(numsSize, sizeof(bool));
int unmarkedSum = 0;
for (int i = 0; i < numsSize; i++) unmarkedSum += nums[i];
Element* elems = (Element*)malloc(numsSize * sizeof(Element));
for (int i = 0; i < numsSize; i++) {
elems[i].value = nums[i];
elems[i].index = i;
}
qsort(elems, numsSize, sizeof(Element), compareElements);
*resultSize = queriesSize;
int* result = (int*)malloc(queriesSize * sizeof(int));
for (int q = 0; q < queriesSize; q++) {
int index = queries[q][0];
int k = queries[q][1];
if (!marked[index]) {
marked[index] = true;
unmarkedSum -= nums[index];
}
int count = 0;
for (int i = 0; i < numsSize && count < k; i++) {
if (!marked[elems[i].index]) {
marked[elems[i].index] = true;
unmarkedSum -= elems[i].value;
count++;
}
}
result[q] = unmarkedSum;
}
free(elems);
free(marked);
return result;
}
int main() {
int nums[] = {1, 2, 2, 1, 2, 3, 1};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int query1[] = {1, 2};
int query2[] = {3, 3};
int query3[] = {4, 2};
int* queries[] = {query1, query2, query3};
int queriesSize = sizeof(queries) / sizeof(queries[0]);
int resultSize;
int* result = markElements(nums, numsSize, queries, queriesSize, &resultSize);
for (int i = 0; i < resultSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] MarkElements(int[] nums, int[][] queries) {
int n = nums.Length;
var marked = new HashSet<int>();
int unmarkedSum = nums.Sum();
var sortedList = nums
.Select((value, index) => new { value, index })
.OrderBy(pair => pair.value)
.ThenBy(pair => pair.index)
.ToList();
var result = new List<int>();
foreach (var query in queries) {
int index = query[0];
int k = query[1];
if (!marked.Contains(index)) {
marked.Add(index);
unmarkedSum -= nums[index];
}
int count = 0;
for (int i = 0; i < sortedList.Count && count < k; i++) {
int idx = sortedList[i].index;
if (!marked.Contains(idx)) {
marked.Add(idx);
unmarkedSum -= sortedList[i].value;
count++;
}
}
result.Add(unmarkedSum);
}
return result.ToArray();
}
// Example usage
public static void Main() {
Solution solution = new Solution();
int[] nums = { 1, 2, 2, 1, 2, 3, 1 };
int[][] queries = { new[] { 1, 2 }, new[] { 3, 3 }, new[] { 4, 2 } };
var result = solution.MarkElements(nums, queries);
Console.WriteLine(string.Join(", ", result));
}
}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.
Space Complexity: O(n), for storing sorted pairs.
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.
function unmarkedSumArray(nums: number[], queries: number[][]): number[] {
const n = nums.length;
let s = nums.reduce((acc, x) => acc + x, 0);
const mark: boolean[] = Array(n).fill(false);
const arr = nums.map((x, i) => [x, i]);
arr.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
let j = 0;
const ans: number[] = [];
for (let [index, k] of queries) {
if (!mark[index]) {
mark[index] = true;
s -= nums[index];
}
for (; k && j < n; ++j) {
if (!mark[arr[j][1]]) {
mark[arr[j][1]] = true;
s -= arr[j][0];
--k;
}
}
ans.push(s);
}
return ans;
}func unmarkedSumArray(nums []int, queries [][]int) []int64 {
n := len(nums)
var s int64
for _, x := range nums {
s += int64(x)
}
mark := make([]bool, n)
arr := make([][2]int, 0, n)
for i, x := range nums {
arr = append(arr, [2]int{x, 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]
})
ans := make([]int64, len(queries))
j := 0
for i, q := range queries {
index, k := q[0], q[1]
if !mark[index] {
mark[index] = true
s -= int64(nums[index])
}
for ; k > 0 && j < n; j++ {
if !mark[arr[j][1]] {
mark[arr[j][1]] = true
s -= int64(arr[j][0])
k--
}
}
ans[i] = s
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Heap and Set Approach | 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. |
| Sorted Index and Two-Pointer Approach | Time Complexity: O(n log n + m * n), as sorting is followed by iteration. Space Complexity: O(n), for storing sorted pairs. |
| Sorting + Simulation | – |
Complexity analysis
| Approach | Time | Space | When 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 Pointer | O(n log n + n + q) | O(n) | Better when elements are consumed once. Replaces heap operations with a single sort and linear scan. |
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.