Abstract / Summary

Given a list and a set of queries, mark elements as true if they match any query's conditions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Heap (Priority Queue)
• Simulation
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution.unmarkedSumArray method processes a list of integers nums together with a series of queries. Each query consists of an index and a count k. The method maintains a running sum of the elements that have not been marked. For every query it first marks the element at the supplied index (if it is not already marked) and then marks up to k additional smallest unmarked elements. After performing these markings the current unmarked sum is yielded. The implementation relies on a boolean array to track marked positions, a pre-sorted iterator to retrieve the smallest remaining values, and an incremental update of the total sum.

Initialization

size = len(nums)

all  = iter(sorted(range(size), key = lambda x : nums[x]))

marked = [ False ] * size
total  = sum(nums)

The length of nums is stored in size. all is an iterator over the indices of nums sorted by their corresponding values; this iterator supplies the smallest unmarked index on demand. marked is a list of flags, one per element, all initially False. total holds the sum of all elements and will be decremented whenever an element becomes marked.

Processing a Single Query

Marking the Explicit Index

for index, k in queries:
    if not marked[index]:
        marked[index] = True
        total -= nums[index]

The loop extracts index and k from each query. If the element at index has not been marked yet, it is marked and its value is subtracted from total. This step guarantees that the explicit request in the query is respected even when the element was previously marked by an earlier query.

Marking Up to k Smallest Unmarked Elements

    for _ in range(k):
        if total == 0:
            break

        while marked[index]:
            index = next(all)
        marked[index] = True
        total -= nums[index]

The inner loop repeats at most k times. The early exit when total == 0 handles the situation where all elements have already been marked, preventing unnecessary iterator advancement.

The while marked[index] clause advances the index variable using the pre-sorted iterator all until an unmarked position is found. Because all yields indices in ascending order of their values, the first unmarked index encountered corresponds to the smallest remaining number. Once such an index is located, it is marked and its contribution is removed from total.

Yielding the Result

    yield total

After completing the explicit and the k-based markings for the current query, the method yields the current sum of all unmarked numbers. The use of a generator (yield) allows the caller to retrieve results lazily, one per query, without constructing an intermediate list.

Edge Cases Handled

When the query’s index points to an element that has already been marked, the conditional guard if not marked[index] prevents double subtraction from total.

If the number of remaining unmarked elements is fewer than k, the inner loop terminates early either because total becomes zero (all values have been removed) or because the iterator all exhausts the list of indices. The while marked[index] construct safely skips over already marked entries, ensuring that the loop never attempts to mark the same element twice.

When nums contains duplicate values, the sorting key lambda x: nums[x] preserves the original index order for equal values, guaranteeing deterministic selection of the smallest unmarked element.

If queries is empty, the outer for loop never executes and the generator produces no output, which is a valid behavior for an empty query set.

Performance Optimizations

The algorithm avoids recomputing the sum of unmarked elements after each query by maintaining total incrementally. Each marking operation reduces total by the exact value of the newly marked element, resulting in constant-time updates.

Sorting the indices once at the start and storing the result in an iterator (all) eliminates the need for repeated scans of nums to locate the smallest unmarked value. The iterator advances monotonically, so each index is examined at most once throughout the entire execution, providing an overall linear pass over the sorted order.

The boolean marked array enables O(1) checks for whether a particular index has already been processed, which is essential for the while marked[index] loop to skip over previously marked entries without additional data structures.

By using a generator (yield) instead of building a list of results, the method reduces memory pressure, especially when the number of queries is large, because only the current result needs to be held in memory at any moment.

The early break condition if total == 0 prevents unnecessary iterations once all elements are marked, saving time in cases where later queries request more markings than remain.

Overall, the combination of a pre-sorted iterator, constant-time sum updates, and lazy result production yields an implementation that scales efficiently with the size of nums and the number of queries.

Imagine a long train of toy boxes lined up in a row, where each box has a different number written on the front. Some numbers are very small and some are quite large. The goal is to keep track of the total sum of all the numbers in the boxes that have not been marked yet. Everyone starts with all boxes open and ready to count.

When playing the game, a helper gives instructions in pairs. The first instruction says to look at a specific box in the line. If that box is not marked, it gets a big red sticker on it, and its number is taken away from the total sum.

The next instruction says to go find the smallest available numbers in the entire train and mark those too, one by one, until a certain number of them are covered with stickers. To do this quickly, the numbers have been pre-sorted from smallest to largest. If the smallest number is already marked, the game skips past it until it finds a fresh one that is still empty. Every time a new box gets a sticker, its number is subtracted from the total sum.

This keeps happening for every set of instructions. After each step, the current total of the remaining unmarked boxes is announced so the game knows how many points are left. The process continues until all the instructions are finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	C++		Python	TS
	WalkCCC	Java	C++		Python
	leetcode.ca	Java	C++	Go	Python	TS
	Progiez	Java	C++		Python
github	charles-wangkai	Java
	fsq		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality