Abstract / Summary

Choose a group of engineers and managers to maximize efficiency times the number of people without exceeding the manager 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 48% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Heap (Priority Queue)
• 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 function computes the maximum possible performance of a team formed from n engineers. Each engineer is described by a speed and an efficiency value. Performance is defined as the product of the sum of speeds of the selected engineers and the minimum efficiency among them. The algorithm selects up to k engineers to maximize this product and returns the result modulo 1,000,000,007.

Preparing the Engineer Data

The first step pairs each engineer’s efficiency with its speed and orders the pairs so that the most efficient engineers are processed first.

all = [(e, s) for e, s in zip(efficiency, speed)]
all.sort(reverse=True)

Sorting in descending order of efficiency guarantees that when the algorithm reaches a particular engineer, that engineer’s efficiency is the smallest efficiency in the current team. This property allows the product total * e to represent the exact performance for the current team composition.

Initializing Accumulators

Two variables are created to keep track of the best performance seen so far (result) and the cumulative speed of the engineers currently in the team (total).

result = 0
total = 0  # sum(speed of selected engineers)

Both start at zero because an empty team yields zero performance.

Maintaining a Bounded Team with a Min-Heap

A min-heap named team stores the speeds of the engineers that are currently part of the candidate team. The heap enables efficient removal of the slowest engineer whenever the team size would exceed the allowed limit k.

team = []
for e, s in all:
    total += s
    heappush(team, s)

    if len(team) > k:
        total -= heappop(team)

When a new engineer is added, its speed is added to total and pushed onto the heap. If the heap size becomes larger than k, the smallest speed (the slowest engineer) is popped, and its speed is subtracted from total. This ensures that the team always contains at most k engineers and that the sum of speeds reflects the fastest possible combination for the current efficiency threshold.

Updating the Best Performance

After adjusting the team size, the algorithm computes the performance for the current configuration. Because the loop processes engineers in decreasing efficiency order, the current engineer’s efficiency e is the minimum efficiency of the team. Multiplying total by e yields the performance for this team, and result is updated if this value is larger.

    result = max(result, total * e)

The max function guarantees that result always holds the highest performance observed across all iterations.

Final Modulo Operation

The problem statement requires the answer modulo 1,000,000,007. The function applies the modulo operation only once, after the loop has finished, to avoid repeated reductions that could affect intermediate calculations.

return result % 1_000_000_007

Edge Cases Handled

When k is larger than or equal to n, the condition len(team) > k never triggers, so the algorithm retains all engineers. The heap therefore simply accumulates all speeds, and the final performance uses the sum of all speeds multiplied by the smallest efficiency (the last engineer processed).

If any engineer has a speed of zero, adding that engineer does not change total. The heap still stores the zero value, and if the team size exceeds k, the zero may be removed without affecting the sum. This behavior correctly handles engineers that contribute no speed.

When all efficiencies are identical, the sorting step preserves the original order of speeds, but the algorithm still correctly evaluates every possible prefix of the sorted list, ensuring the optimal subset is considered.

If k equals one, the heap never exceeds size one, so each iteration evaluates a team consisting solely of the current engineer. The result becomes the maximum of speed[i] * efficiency[i] across all engineers, which matches the definition of performance for a single-member team.

Performance Optimizations

The algorithm leverages sorting to impose a monotonic relationship between the current engineer’s efficiency and the minimum efficiency of the team. This eliminates the need for nested loops that would otherwise recompute the minimum efficiency for each subset.

Using a min-heap to store speeds provides O(log k) insertion and removal, allowing the algorithm to maintain the sum of the fastest k speeds without scanning the entire team on each iteration. The heap size never exceeds k, keeping the memory footprint bounded.

Incremental updates to total avoid recomputing the sum of speeds from scratch after each insertion or removal. By adjusting total only when an engineer is added or the slowest engineer is removed, the algorithm performs a constant amount of work per iteration aside from heap operations.

Deferring the modulo operation until the final return avoids the overhead of repeated modular reductions and ensures that intermediate products remain exact, which is important for preserving the correctness of the maximum comparison.

Imagine building a team of super engineers to finish a puzzle. You have piles of cards that tell you how fast each person works and how clever they are. To make the best team, you start by lining up all the engineers starting with the most clever ones first. Then you look at them one by one. As you pick each person, you add their speed to your total and keep track of who is in your group. If you pick too many people, you find the slowest person in the group and say goodbye to them to make room for someone better. After every step, you multiply your total speed by the cleverness of the person you just looked at to see if this new group is the very best one yet. You keep doing this until you have checked everybody, and then you know which group works the fastest.

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	C++	Java		Python		TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python	Go
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	fsq	C++
	halfrost					Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007				Python
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
varunu28	Java
vthwang	Java
wisdompeak	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