#3080

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Mark Elements on Array by Performing Queries

Efficiently mark elements in an array based on queries using scanning plus hash lookup to track marked indices and compute sums.

array hash table sorting heap priority queue simulation

Problem Statement

You are given a 0-indexed array nums of positive integers and a 2D array queries where each query specifies an index and a count ki. Initially, all elements are unmarked. For each query, you mark the element at the given index and the ki smallest unmarked elements, then compute the sum of remaining unmarked elements after marking.

Return an array where each element corresponds to the sum of unmarked elements after performing the respective query. The challenge is efficiently tracking which elements are already marked and avoiding repeated scanning of the entire array for each query.

Examples

Example 1

Input: nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]

Output: [8,3,0]

We do the following queries on the array:

Example 2

Input: nums = [1,4,2,3], queries = [[0,1]]

Output: [7]

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

Solution Approach

Use a Hash Table to Track Marked Indices

Create a boolean or hash table array the same length as nums to record which indices are marked. This prevents double-counting when processing queries and allows constant-time checks during each query operation.

Process Queries with Sorted Access

Sort a copy of nums along with their original indices. For each query, select the ki smallest unmarked elements quickly using the sorted array while updating the hash table, reducing repeated scanning overhead.

Compute Unmarked Sums Efficiently

Maintain a running total of unmarked elements or update the sum incrementally after marking. This avoids recomputing the sum of the entire array after each query and ties directly to the failure mode of naive repeated summation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on sorting nums once (O(n log n)) and processing m queries with O(1) hash checks per element. Space complexity is O(n) for the hash table tracking marked elements.

What Interviewers Usually Probe

They may ask how you avoid double-counting marked elements across queries.
They may hint at using additional data structures like hash tables to track marks.
They may suggest considering sorting to quickly find the ki smallest unmarked elements.

Common Pitfalls or Variants

Common pitfalls

Recomputing the sum of unmarked elements from scratch after every query.
Marking elements without checking if they are already marked, causing errors.
Ignoring the optimal combination of array scanning and hash lookup, leading to TLE.

Follow-up variants

Instead of marking the smallest ki elements, mark the largest ki elements and compute sums.
Allow queries that mark ranges instead of single indices, requiring interval tracking.
Modify nums dynamically between queries, needing a flexible update strategy.

FAQ

What is the main pattern used in Mark Elements on Array by Performing Queries?

The key pattern is array scanning combined with hash table lookup to track marked elements efficiently.

Can I avoid sorting to solve this problem?

Sorting is optional but helps quickly identify the ki smallest unmarked elements; skipping it may require more complex selection logic.

How do I track which elements are already marked?

Use a boolean array or hash table indexed by element positions to record which elements are marked to prevent double-counting.

What is the time complexity for processing all queries?

Sorting costs O(n log n) once, then each query uses O(ki) hash lookups; overall complexity depends on the sum of all ki across queries.

Why does naive repeated sum computation fail?

Recomputing the sum of unmarked elements from scratch after each query results in O(n * m) time, which exceeds limits for large arrays.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        s = sum(nums)
        mark = [False] * n
        arr = sorted((x, i) for i, x in enumerate(nums))
        j = 0
        ans = []
        for index, k in queries:
            if not mark[index]:
                mark[index] = True
                s -= nums[index]
            while k and j < n:
                if not mark[arr[j][1]]:
                    mark[arr[j][1]] = True
                    s -= arr[j][0]
                    k -= 1
                j += 1
            ans.append(s)
        return ans

Continue Practicing

#2593 find score of an array after marking all elements #2402 meeting rooms iii #2357 make array zero by subtracting equal amounts