Maximum Performance of a Team: Sort + Min-Heap

You are given n engineers numbered from 1 to n, along with two arrays: speed[i] and efficiency[i]. You need to form a team of at most k engineers to maximize performance, defined as sum(speed) * min(efficiency) of the chosen engineers. Return the result modulo 10^9 + 7.

This is LeetCode 1383: Maximum Performance of a Team, a hard problem that combines sorting with a min-heap in a way that feels magical once you see the trick. The key is reducing a two-dimensional optimization into a one-dimensional scan.

Why this problem matters

This problem is one of the cleanest examples of the "sort by one dimension, optimize the other with a heap" pattern. You will see this same structure in problems like IPO (LeetCode 502), where you sort projects by capital and use a heap to pick the most profitable ones, and in meeting scheduling problems where you sort by start time and track end times with a heap.

The pattern is powerful because it eliminates one variable entirely. By sorting, you guarantee that one quantity (here, efficiency) is monotonically handled, and you use a heap to greedily optimize the other (speed). Mastering this combination unlocks an entire family of greedy problems.

The key insight

The performance formula is sum(speed) * min(efficiency). The min(efficiency) term is the bottleneck. If you sort engineers by efficiency in descending order and iterate through them, the current engineer always has the lowest efficiency of anyone you have considered so far. That means the current engineer's efficiency is always the min(efficiency) for any team that includes them.

With that variable pinned, you just need to maximize sum(speed). You do that with a min-heap of size k: keep the k largest speeds seen so far. If adding a new engineer's speed would push the heap past size k, pop the smallest speed. At each step, calculate sum_of_speeds * current_efficiency and track the maximum.

This works because even though you might pop an engineer with a higher efficiency, you already computed the performance for any team that included them. You never miss the optimal answer.

The solution

import heapq

def max_performance(n, speed, efficiency, k):
    MOD = 10**9 + 7
    engineers = sorted(zip(efficiency, speed), reverse=True)
    heap = []
    speed_sum = 0
    best = 0

    for eff, spd in engineers:
        heapq.heappush(heap, spd)
        speed_sum += spd

        if len(heap) > k:
            speed_sum -= heapq.heappop(heap)

        best = max(best, speed_sum * eff)

    return best % MOD

Here is what each piece does:

1. Pair and sort. Zip efficiency and speed together, then sort by efficiency descending. This ensures that as you iterate, each engineer has the smallest efficiency seen so far.
2. Min-heap of speeds. Push each engineer's speed into a min-heap. If the heap grows beyond k, pop the smallest speed. This keeps only the k largest speeds in the heap.
3. Track the running sum. Maintain speed_sum as the total of all speeds in the heap. When you pop, subtract the popped value.
4. Compute performance. At each step, multiply speed_sum by the current efficiency (which is the minimum for this team). Update best if this product is larger.
5. Return modulo. The problem asks for the result modulo 10^9 + 7, so apply it at the end.

Visual walkthrough

Walking through speed = [2, 10, 3, 1, 5], efficiency = [5, 4, 3, 2, 1], k = 2:

After sorting by efficiency descending, we process engineers in order of decreasing efficiency. At step 2, we form the team with speeds [2, 10] and minimum efficiency 4, giving performance 48. No later combination beats this because the efficiency only decreases while the speed sum cannot grow fast enough to compensate.

Complexity analysis

Time: Sorting takes O(n log n). Iterating through n engineers with heap operations (each O(log k)) adds O(n log k). Since k is at most n, the total is O(n log n).

Space: The sorted array and heap together use O(n).

The building blocks

1. Sort by one dimension

When your objective involves two variables and one of them appears inside a min or max, sort by that dimension. This pins its value at each step and reduces the problem to optimizing the other variable.

engineers = sorted(zip(efficiency, speed), reverse=True)

By sorting efficiency descending, the current engineer's efficiency is always the team minimum. You no longer need to search for the minimum. It is always the engineer you just added.

2. Min-heap to maintain top-k speeds

A min-heap of bounded size k keeps the k largest values seen so far. The root is the smallest of the top k, so when a new value arrives that is larger than the root, you swap it in.

heapq.heappush(heap, spd)
speed_sum += spd
if len(heap) > k:
    speed_sum -= heapq.heappop(heap)

This is the same building block used in Kth Largest Element in an Array, but here you also maintain a running sum. The key detail is updating speed_sum on both push and pop so you always know the total without re-summing.

Edge cases

• k = 1. You want the single engineer with the highest speed * efficiency. The heap has size 1, so you just track the best individual performance.
• k = n. You can include all engineers. The heap never needs to pop, so the answer is sum(all speeds) * min(all efficiencies). But the algorithm still checks subsets along the way, which might score higher.
• All equal efficiencies. When every engineer has the same efficiency, the min is always that value. The problem reduces to picking the k engineers with the highest speeds.
• Single engineer. n = 1, k = 1. Return speed[0] * efficiency[0] % MOD.
• Large values. Speeds and efficiencies can be up to 10^5 with n up to 10^5. The product can exceed 10^10, so use a language that supports big integers or be careful with overflow. Python handles this naturally.

From understanding to recall

The sort-then-heap pattern makes sense when you read it, but recreating it from scratch is where most people stumble. The details matter: sorting by efficiency descending (not ascending), using a min-heap (not max-heap), and remembering to track the running sum alongside the heap. Under interview pressure, it is easy to sort in the wrong direction or forget to subtract the popped value from the sum.

Spaced repetition fixes this. You write the solution from scratch at increasing intervals until the pattern becomes automatic. You see "maximize sum times min" and immediately reach for sort-by-min-descending plus a bounded heap. A few focused reps and the implementation flows without hesitation.

Related posts

• Kth Largest Element in an Array - Uses the same min-heap-of-size-k building block to find the kth largest in O(n log k)
• Top K Frequent Elements - Another heap-based selection problem where you maintain a bounded heap of size k
• Task Scheduler - A greedy scheduling problem where sorting and priority queues combine to find the optimal arrangement

CodeBricks breaks this problem into its sort-by-one-dimension and bounded-min-heap building blocks, then drills them independently with spaced repetition. You practice each piece from scratch until the pattern is muscle memory. When a sort-plus-heap problem shows up in your interview, you do not hesitate. You just write it.