Maximum Performance of a Team — Sort + Min-Heap Greedy Interview

Problem Statement#

You have n engineers with speed and efficiency arrays. Pick at most k engineers to maximize team performance, defined as (sum of selected speeds) * (minimum selected efficiency). Return the answer modulo 10^9 + 7.

Constraints:

• 1 <= k <= n <= 10^5
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8

Input:  n=6, speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=2
Output: 60

Input:  n=6, speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=3
Output: 68

Why This Problem Matters#

LeetCode 1383 is a Google, Amazon, and Meta hard interview problem that combines greedy sorting with a min-heap. It is the textbook "fix one factor, optimize the other" pattern: by iterating engineers in decreasing efficiency order, every prefix sees a known minimum efficiency, so you only need to maximize the sum of speeds among the top-k speeds.

This priority queue interview pattern reuses for K closest sums, top-k weighted, and online team selection. It is a heap FAANG interview staple.

The Core Insight#

Sort engineers by efficiency descending. Iterate; at each engineer i, all previously seen engineers have efficiency >= efficiency[i]. Maintain a size-k min-heap of speeds. Push current speed; if heap size exceeds k, pop the smallest. The candidate answer is sum_speeds * efficiency[i]. Track the max.

Visual Dry Run#

speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=3 Sorted by efficiency desc: (eff,speed) = [(9,1),(7,5),(5,2),(4,10),(3,3),(2,8)]

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        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

class MinHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i] < this.h[p]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l] < this.h[m]) m = l;
            if (r < n && this.h[r] < this.h[m]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}
 
var maxPerformance = function(n, speed, efficiency, k) {
    const MOD = 1_000_000_007n;
    const engineers = efficiency.map((e, i) => [e, speed[i]]);
    engineers.sort((a, b) => b[0] - a[0]);
    const heap = new MinHeap();
    let speedSum = 0n, best = 0n;
    for (const [eff, spd] of engineers) {
        heap.push(spd);
        speedSum += BigInt(spd);
        if (heap.size > k) speedSum -= BigInt(heap.pop());
        const cand = speedSum * BigInt(eff);
        if (cand > best) best = cand;
    }
    return Number(best % MOD);
};

Time: O(N log N) — sorting plus N heap operations. Space: O(N) — heap and sorted array.

Common Mistakes#

• Applying the modulo too early; modulo destroys ordering for max comparison.
• Sorting by speed instead of efficiency.
• Forgetting that team size can be less than k; tracking best at every iteration handles this.
• Using a max-heap and trying to keep the smallest k — wrong polarity.
• Comparing len(heap) >= k instead of > k — off by one.

Interview Tips#

• Verbalize the "fix the bottleneck efficiency" insight.
• Walk through k=2 by hand; show how the heap shrinks past max size.
• Discuss why sorting ascending fails: you would not know the minimum efficiency yet.
• Mention BigInt or Python ints to handle 10^5 * 10^5 * 10^8 = 10^18 overflow.

Follow-up Questions#

• What if you must pick exactly k? Hint: track best only when heap.size == k.
• What if performance is sum_speeds + min_efficiency? Hint: different objective; greedy still works.
• Add a budget per engineer cost. Hint: knapsack plus heap (much harder).
• Stream version where engineers arrive online. Hint: same algorithm, sort by arrival of efficiency tier.
• Find which engineers form the best team. Hint: track the heap snapshot at the best step.

Key Takeaways#

• LeetCode 1383 Maximum Performance of a Team is a sorted-sweep min-heap problem.
• Sort by efficiency descending so the minimum is always the current engineer.
• Maintain a size-k min-heap of speeds to keep the largest k.
• Time: O(N log N). Space: O(N).
• Apply modulo only at the end.
• Pattern reuses for top-k weighted selection problems.
• A favorite Google and Amazon priority queue interview hard problem.