Maximum Performance of a Team — Problem & Solution
Maximum Performance of a Team solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Performance of a Team is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n engineers, each with a speed and an efficiency. The performance of a team is the sum of its speeds multiplied by the minimum efficiency among its members.
Pick at most k engineers to maximise the performance, and return it modulo 10^9 + 7.
Example 1
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: Engineers 1 and 4: `(10 + 5) × min(4, 7) = 15 × 4`.
Example 2
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Example 3
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72
Constraints
1 <= k <= n <= 1000speed.length == efficiency.length == n1 <= speed[i] <= 10^51 <= efficiency[i] <= 10^5
Hints for Maximum Performance of a Team
Hint 1
Sort the engineers by efficiency, highest first.
Hint 2
Sweeping in that order, the engineer just added always has the lowest efficiency in the team.
Hint 3
Keep the
kfastest speeds seen so far in a min-heap and score at every step.
How to solve Maximum Performance of a Team
Sort by efficiency descending. At each step the current engineer fixes the team's minimum efficiency, so the best team ending there takes the k largest speeds among those seen — maintained by a size-k min-heap.
Approach
- Sort the indices by efficiency, largest first.
- Push each speed onto a min-heap and add it to a running sum.
- If the heap exceeds
k, pop the smallest speed and subtract it. - Score
sum × efficiency[current]and keep the maximum; apply the modulus only at the end.
Why it works
The team may hold at most k engineers, so the score is taken at every step, not only once the heap is full — a smaller team with a very high minimum efficiency can win. Dropping the slowest engineer when the heap overflows is safe: they can never improve the sum for this or any later minimum.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Applying the modulus while comparing candidates picks the wrong maximum — reduce only at the end.
- Scoring only when the team is full misses the smaller high-efficiency teams.
- The products exceed a 32-bit int, so the running work needs a 64-bit accumulator.
Reference solution
Python
from typing import List
import heapq
def maxPerformance(n: int, speed: List[int], efficiency: List[int], k: int) -> int:
MOD = 1000000007
order = sorted(range(n), key=lambda i: -efficiency[i])
heap = []
total = 0
best = 0
for i in order:
heapq.heappush(heap, speed[i])
total += speed[i]
if len(heap) > k:
total -= heapq.heappop(heap)
best = max(best, total * efficiency[i])
return best % MODJava
public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
final long MOD = 1000000007L;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> efficiency[b] - efficiency[a]);
PriorityQueue<Integer> heap = new PriorityQueue<>();
long sum = 0, best = 0;
for (int i : order) {
heap.add(speed[i]);
sum += speed[i];
if (heap.size() > k) sum -= heap.poll();
best = Math.max(best, sum * efficiency[i]);
}
return (int) (best % MOD);
}C++
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
const long long MOD = 1000000007;
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return efficiency[a] > efficiency[b]; });
priority_queue<int, vector<int>, greater<int>> heap;
long long sum = 0, best = 0;
for (int i : order) {
heap.push(speed[i]);
sum += speed[i];
if ((int) heap.size() > k) {
sum -= heap.top();
heap.pop();
}
best = max(best, sum * efficiency[i]);
}
return (int) (best % MOD);
}JavaScript
var maxPerformance = function(n, speed, efficiency, k) {
var MOD = 1000000007, i;
var order = [];
for (i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return efficiency[b] - efficiency[a]; });
var heap = [];
var push = function(v) {
heap.push(v);
var j = heap.length - 1;
while (j > 0) {
var p = (j - 1) >> 1;
if (heap[p] <= heap[j]) break;
var t = heap[p]; heap[p] = heap[j]; heap[j] = t;
j = p;
}
};
var pop = function() {
var top = heap[0];
var last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === j) break;
var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
j = s;
}
}
return top;
};
var sum = 0, best = 0;
for (var t2 = 0; t2 < order.length; t2++) {
var idx = order[t2];
push(speed[idx]);
sum += speed[idx];
if (heap.length > k) sum -= pop();
var perf = sum * efficiency[idx];
if (perf > best) best = perf;
}
return best % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms