3080. Mark Elements on Array by Performing Queries LeetCode Solution
In this guide, you will get 3080. Mark Elements on Array by Performing Queries LeetCode Solution with the best time and space complexity. The solution to Mark Elements on Array by Performing Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Mark Elements on Array by Performing Queries
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
Complexity Analysis
Time Complexity: O(n\log n + m\log n)
Space Complexity: O(n)
3080. Mark Elements on Array by Performing Queries LeetCode Solution in C++
class Solution {
public:
vector<long long> unmarkedSumArray(vector<int>& nums,
vector<vector<int>>& queries) {
vector<long long> ans;
vector<bool> marked(nums.size());
long sum = accumulate(nums.begin(), nums.end(), 0L);
using P = pair<int, int>; // (nums[i], i)
priority_queue<P, vector<P>, greater<>> minHeap;
for (int i = 0; i < nums.size(); ++i)
minHeap.emplace(nums[i], i);
for (const vector<int>& query : queries) {
const int index = query[0];
const int k = query[1];
if (!marked[index]) {
marked[index] = true;
sum -= nums[index];
}
for (int popped = 0; popped < k && !minHeap.empty();) {
const auto [num, i] = minHeap.top();
minHeap.pop();
if (!marked[i]) {
marked[i] = true;
sum -= num;
++popped;
}
}
ans.push_back(sum);
}
return ans;
}
}; /* code provided by PROGIEZ */
3080. Mark Elements on Array by Performing Queries LeetCode Solution in Java
class Solution {
public long[] unmarkedSumArray(int[] nums, int[][] queries) {
long[] ans = new long[queries.length];
boolean[] marked = new boolean[nums.length];
long sum = Arrays.stream(nums).asLongStream().sum();
// (nums[i], i)
Queue<Pair<Integer, Integer>> minHeap =
new PriorityQueue<>(Comparator.comparing(Pair<Integer, Integer>::getKey)
.thenComparing(Pair<Integer, Integer>::getValue));
for (int i = 0; i < nums.length; ++i)
minHeap.offer(new Pair<>(nums[i], i));
for (int queryIndex = 0; queryIndex < queries.length; ++queryIndex) {
final int index = queries[queryIndex][0];
final int k = queries[queryIndex][1];
if (!marked[index]) {
marked[index] = true;
sum -= nums[index];
}
for (int popped = 0; popped < k && !minHeap.isEmpty();) {
final int num = minHeap.peek().getKey();
final int i = minHeap.poll().getValue();
if (!marked[i]) {
marked[i] = true;
sum -= num;
++popped;
}
}
ans[queryIndex] = sum;
}
return ans;
}
} // code provided by PROGIEZ
3080. Mark Elements on Array by Performing Queries LeetCode Solution in Python
class Solution:
def unmarkedSumArray(
self,
nums: list[int],
queries: list[list[int]],
) -> list[int]:
ans = []
marked = set()
summ = sum(nums)
minHeap = [(num, i) for i, num in enumerate(nums)]
heapq.heapify(minHeap)
for index, k in queries:
if index not in marked:
marked.add(index)
summ -= nums[index]
popped = 0
while popped < k and minHeap:
num, i = heapq.heappop(minHeap)
if i not in marked:
marked.add(i)
summ -= num
popped += 1
ans.append(summ)
return ans # code by PROGIEZ
