Maximum Performance of a Team

Hard
975.

Maximum Performance of a Team

Maximum Performance of a Team is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

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 <= 1000
  • speed.length == efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} speed
 * @param {number[]} efficiency
 * @param {number} k
 * @return {number}
 */
var maxPerformance = function(n, speed, efficiency, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • speed.length == efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^5

Hints for Maximum Performance of a Team

  1. Hint 1

    Sort the engineers by efficiency, highest first.

  2. Hint 2

    Sweeping in that order, the engineer just added always has the lowest efficiency in the team.

  3. Hint 3

    Keep the k fastest 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

  1. Sort the indices by efficiency, largest first.
  2. Push each speed onto a min-heap and add it to a running sum.
  3. If the heap exceeds k, pop the smallest speed and subtract it.
  4. 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 % MOD

Java

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