Abstract / Summary

Given a list of numbers and a limit, find the longest subsequence whose sum does not exceed the limit.

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 74% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Greedy
• Prefix Sum
• 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 class implements a method answerQueries that processes a list of integers nums against a series of query thresholds queries. For each query the method determines the maximum count of elements from nums that can be selected without the cumulative sum exceeding the query value. The algorithm iterates through nums while maintaining a dynamic collection of chosen numbers using a heap, adjusting the collection whenever the running total would violate the current query limit. The result for each query is produced as a generator value.

Core Logic

The method begins by iterating over each query value. For every query a fresh set of local variables is created:

for q in queries:
    have   = []
    total  = 0
    length = 0

have serves as a heap that stores the selected numbers as their negative values, effectively turning Python’s min-heap into a max-heap. total accumulates the sum of the numbers currently in the heap, and length records the greatest size the heap attains during the scan of nums.

The inner loop walks through the original array:

for n in nums:
    heappush(have, -n)
    total += n
    if total > q:
        total -= -heappop(have)
    length = max(length, len(have))

Each element n is pushed onto the heap (as -n). The running sum total is increased by n. If adding n pushes the sum beyond the query limit q, the algorithm removes the largest element seen so far by popping the heap’s top (which corresponds to the most negative entry, i.e., the largest original number). The removed value is subtracted from total, restoring the sum to a permissible level. After each insertion (and possible removal) the current heap size is compared with length, ensuring that length always reflects the maximum number of elements that could be kept without exceeding the query.

When the inner loop finishes, the method yields the final length for that query:

yield length

Because the method uses a generator (yield), callers can iterate over the results lazily, receiving each answer as soon as it is computed.

Edge Cases Handled

When nums is empty, the inner loop never executes, leaving length at its initial value of zero. Consequently the generator yields 0 for every query, correctly indicating that no elements can be selected.

If a query value q is smaller than any individual element in nums, the first insertion will cause total to exceed q. The subsequent removal step immediately discards the just-added element, keeping the heap empty and total at zero. The algorithm therefore yields 0 for that query, reflecting the impossibility of selecting any number without breaching the limit.

When multiple identical numbers appear in nums, each instance is treated independently. The heap stores each occurrence as a separate entry, and removal always targets the largest value present, which may be one of several equal maxima. This behavior ensures that the count reflects the true maximum cardinality achievable under the sum constraint.

If a query value is extremely large-larger than the sum of all elements in nums-the condition total > q never triggers. The heap simply accumulates every element, and length ends up equal to the length of nums. The yielded answer correctly reports that all numbers can be taken.

The generator design also gracefully handles an empty queries list: the outer loop never runs, and the method produces no output, matching the expectation of zero answers.

Performance Optimizations

The algorithm leverages a max-heap implemented via negated values, allowing constant-time access to the current largest element. By pushing each new number onto the heap and only removing when the sum exceeds the query, the method avoids scanning the entire collection to find the maximum each time, which would be costly.

Maintaining the running sum total eliminates the need to recompute the sum of the heap after each modification. The subtraction performed during removal directly adjusts total by the exact value that was discarded, keeping the sum accurate with minimal overhead.

Updating length with max(length, len(have)) after each iteration ensures that the algorithm records the best achievable count without storing intermediate states or performing additional passes.

Finally, using a generator (yield) means that memory consumption is limited to the state required for a single query at a time. The heap and counters are reinitialized for each query, preventing the accumulation of data across queries and keeping the memory footprint proportional to the size of nums rather than the product of len(nums) and len(queries).

Imagine you have a big treasure box full of smaller boxes of different sizes. There is a special rule for each mission you get. For every mission, you want to fit as many boxes as possible into your bag without the total weight going over the limit set by the mission.

You start by picking up boxes one by one and putting them into your bag. As you pick them up, keep track of how much weight you have inside. If the total weight gets too heavy and crosses the limit of the mission, you look at all the boxes currently in your bag and find the heaviest one. You take that big, heavy box out of your bag and put it back on the floor. Now your bag is lighter, and you can keep adding smaller boxes until you cannot add any more without breaking the limit.

You do this for every mission you receive. For each mission, you count how many boxes stayed in your bag at the very end. That count shows how many boxes you successfully kept for that specific mission. Once you finish one mission, you start again with all the boxes on the floor for the next mission.

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

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Python			C++					TS
	WalkCCC	Java	Python			C++
	leetcode.ca	Java	Python	JS		C++		C#	Go	Rust	TS
	Progiez	Java	Python			C++
github	charles-wangkai	Java
	DimitrisJim						C
	everthis			JS
	fartem				Ruby
	fsq					C++
	JoshCrozier			JS
	lkwq007		Python
	trung-hn		Python
	varunu28	Java
	vthwang	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
trung-hn	Python
varunu28	Java
vthwang	Java

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