Abstract / Summary

Given group members and requirements for schemes, count profitable plans that use at most the members and meet minimum group and profit.

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 49% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

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 implementation solves a combinatorial budgeting problem using dynamic programming. It counts the number of ways to select a subset of crimes such that the total number of gangsters used does not exceed a given limit and the accumulated profit meets or exceeds a required threshold. The algorithm builds a state table indexed by the number of gangsters employed and the profit achieved, updating it iteratively for each crime. A modular reduction is applied to keep the result within integer bounds.

Core Data Structures

The solution creates a list named have whose length is one more than the maximum number of gangsters (n). Each entry in this list is a defaultdict(int) that maps a profit value to the count of schemes that achieve that profit with the corresponding number of gangsters. The initial state seeds the table with a single scheme that uses zero gangsters and yields zero profit.

have = [defaultdict(int) for _ in range(n + 1)]
have[0][0] = 1

Preparing the Crime List

The input arrays group and profit are zipped together to form a list of tuples, each representing a crime with its required gangsters and profit. The list is sorted, which stabilizes the order of processing and can improve cache locality during the DP updates.

crimes = [(g, p) for g, p in zip(group, profit)]
for gangsters, gain in sorted(crimes):
    ...

Dynamic Programming Transition

The heart of the algorithm iterates over each crime and updates the DP table in reverse order of gangster count. The reverse traversal (reversed(range(n + 1))) guarantees that each crime contributes to new states only once per iteration, preventing the same crime from being counted multiple times within a single update cycle.

for worked in reversed(range(n + 1)):
    for money, schemes in have[worked].items():
        if worked + gangsters <= n:
            total = money + gain
            total = min(total, minProfit)
            have[worked + gangsters][total] += schemes

Edge Cases Managed in the Transition

• Gangster Capacity Exceeded: The conditional if worked + gangsters <= n ensures that any transition that would surpass the total available gangsters is ignored, naturally handling cases where a crime cannot be accommodated.
• Profit Capping: By applying total = min(total, minProfit), the algorithm collapses all profit values that meet or exceed the required threshold into a single bucket. This reduces the number of distinct profit keys stored, effectively handling large profit values without expanding the DP table unnecessarily.
• Zero-Gangster Scenarios: When n is zero, the outer loop still creates a single entry have[0]. The reverse range iterates over only index zero, and the capacity check prevents any addition, leaving the seed state untouched. This correctly yields a result of one scheme (the empty set) if minProfit is also zero, or zero otherwise.

Aggregating the Result

After processing all crimes, the algorithm scans the DP table to sum the counts of schemes whose profit meets the required minimum. Because profit values have been capped at minProfit, any entry with a key equal to minProfit represents all schemes that achieve at least the threshold.

result = 0
for h in have:
    for money, schemes in h.items():
        if money >= minProfit:
            result += schemes

The final answer is returned modulo 1_000_000_007 to conform to typical large-integer constraints.

return result % modulo

Performance Optimizations

• Profit Bucketing: By capping profit values at minProfit, the DP table’s second dimension is bounded by the profit threshold rather than the sum of all individual profits. This dramatically reduces memory consumption and the number of inner-loop iterations.
• Reverse Iteration: Updating the DP table in reverse order of gangster usage eliminates the need for a secondary table or explicit copying, saving both time and space.
• Sparse Representation: Using defaultdict(int) for each gangster count stores only profit values that have been reached, avoiding a dense two-dimensional array filled with zeros. This sparsity is especially beneficial when many profit combinations are unattainable.
• Sorted Crime List: Sorting the crimes before processing can improve data locality, leading to better cache performance during the nested loops.

Overall, the implementation combines a compact state representation with careful iteration order to efficiently enumerate all feasible crime schemes while respecting the given constraints.

Imagine there is a big team of people who want to carry out some secret missions. Every mission needs a certain number of helpers and gives back a certain amount of treasure. There is also a limit on how many people are allowed to join the team, and a goal for how much treasure needs to be collected by the end.

The code sets up a special notebook to keep track of all the different ways these missions can be organized. It starts with zero missions done and zero treasure found. Think of this as opening a blank page for every possible group size up to the limit.

The code looks at each mission one by one. It decides whether to add a mission to a plan. If there are enough people available to help, it adds the new mission to the set of plans that already exist. By going through the available people in a very specific order, it makes sure each mission is only counted once for each plan.

After checking through every possible combination of missions, the notebook holds the information about every valid way to reach the goal. The last part of the code goes through that notebook and adds up all the different ways that result in having enough treasure to succeed. Because there could be so many ways, it uses a very big number to keep the final count tidy.

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

Time: polynomial
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	C++	Java					Python	TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java				Go	Python
	LeetcodeHelp	C++	Java					Python
	Progiez	C++	Java					Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	gouthampradhan		Java
	JoshCrozier			JS
	ruoru				Rust
	suxrobGM					C#
	varunu28		Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
ruoru	Rust
suxrobGM	C#
varunu28	Java
wisdompeak	C++
zfang399	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