Maximum Performance of a Team

Hard

#1282Time: O(N^2 * logN). The outer loop runs `N` times. Inside, we iterate `N` times to find eligible engineers, and then sort a list of up to `N` elements, which takes `O(N log N)`. This dominates the inner loop, leading to `O(N * (N + N log N)) = O(N^2 log N)`.Space: O(N). In each iteration of the outer loop, we create a list `eligibleSpeeds` which can store up to `N` speeds.5 companies

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

DoorDash Flipkart DE Shaw PhonePe

Prompt

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the i^th engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of its engineers' speeds multiplied by the minimum efficiency among its engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 10⁹ + 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: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 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 <= 10⁵
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10⁵
1 <= efficiency[i] <= 10⁸

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every engineer, considering each one as the member with the minimum efficiency in a potential team. For each chosen minimum efficiency E, it finds the best possible team by gathering all engineers with efficiency greater than or equal to E and picking the k fastest among them.

Algorithm

Initialize max_performance = 0.
For each engineer i from 0 to n-1:
- Set min_eff = efficiency[i].
- Create a list eligible_speeds.
- For each engineer j from 0 to n-1:
  - If efficiency[j] >= min_eff, add speed[j] to eligible_speeds.
- Sort eligible_speeds in descending order.
- Initialize current_speed_sum = 0.
- Iterate through the first min(k, eligible_speeds.size()) elements of eligible_speeds and add them to current_speed_sum.
- Calculate current_performance = current_speed_sum * min_eff.
- Update max_performance = max(max_performance, current_performance).
Return max_performance modulo 10^9 + 7.

Walkthrough

The core idea is that the minimum efficiency of an optimal team must be the efficiency of one of its members. We can iterate through each engineer i and fix their efficiency efficiency[i] as the minimum efficiency for a candidate team. For a fixed minimum efficiency E = efficiency[i], any other engineer j in the team must have efficiency[j] >= E. To maximize the performance (sum of speeds) * E, we need to maximize the sum of speeds. This means we should select up to k engineers from the pool of those with efficiency >= E who have the highest speeds. After calculating the performance for this team, we update our overall maximum. By repeating this for every engineer, we ensure we have checked all possibilities for the minimum efficiency and found the global maximum performance.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {7        long maxPerformance = 0;8        long MOD = 1_000_000_007;9 10        for (int i = 0; i < n; i++) {11            int minEfficiency = efficiency[i];12            List<Integer> eligibleSpeeds = new ArrayList<>();13            for (int j = 0; j < n; j++) {14                if (efficiency[j] >= minEfficiency) {15                    eligibleSpeeds.add(speed[j]);16                }17            }18 19            Collections.sort(eligibleSpeeds, Collections.reverseOrder());20 21            long currentSpeedSum = 0;22            for (int l = 0; l < Math.min(k, eligibleSpeeds.size()); l++) {23                currentSpeedSum += eligibleSpeeds.get(l);24            }25 26            maxPerformance = Math.max(maxPerformance, currentSpeedSum * minEfficiency);27        }28 29        return (int) (maxPerformance % MOD);30    }31}

Complexity

Time

O(N^2 * logN). The outer loop runs `N` times. Inside, we iterate `N` times to find eligible engineers, and then sort a list of up to `N` elements, which takes `O(N log N)`. This dominates the inner loop, leading to `O(N * (N + N log N)) = O(N^2 log N)`.

Space

O(N). In each iteration of the outer loop, we create a list `eligibleSpeeds` which can store up to `N` speeds.

Trade-offs

Pros

Conceptually simpler than the optimal approach.
Correctly identifies the structure of the problem (fixing minimum efficiency).

Cons

Too slow for the given constraints (N <= 10^5), will result in a "Time Limit Exceeded" error.
Repeatedly re-calculates and re-sorts lists of speeds, which is highly inefficient.

This is an efficient approach that avoids redundant computations by processing engineers in a specific order. By sorting engineers by their efficiency in descending order, we can iterate through them and maintain a running team of size k with the highest speeds encountered so far. A min-priority queue is used to efficiently manage this team.

Algorithm

Create a 2D array or a list of objects to store (efficiency, speed) pairs for each engineer.
Sort these pairs in descending order of efficiency.
Initialize a min-priority queue speed_heap.
Initialize speed_sum = 0 and max_performance = 0 (using long to prevent overflow).
For each engineer (E, S) in the sorted list:
- Add the current speed S to speed_heap.
- Add S to speed_sum.
- If speed_heap.size() > k:
  - Remove the minimum speed from the heap: min_speed = speed_heap.poll().
  - Subtract min_speed from speed_sum.
- Calculate current_performance = speed_sum * E.
- Update max_performance = max(max_performance, current_performance).
Return max_performance % (10^9 + 7).

Walkthrough

The key insight is that if we consider engineers in decreasing order of their efficiency, then for any engineer we are currently at, their efficiency is the minimum among all engineers we have seen so far. This allows us to fix the min_efficiency term of the performance formula and focus on maximizing the sum_of_speeds.

The algorithm first pairs up efficiencies and speeds and sorts these pairs by efficiency in descending order. Then, it iterates through the sorted engineers. A min-priority queue (min-heap) is used to maintain the speeds of the current team members. For each engineer, we add their speed to the heap and a running sum. If the team size (heap size) exceeds k, we remove the engineer with the smallest speed (the root of the min-heap) to maintain the team size and keep the sum of speeds as high as possible. At each step, we calculate a potential maximum performance by multiplying the current sum of speeds by the current engineer's efficiency (which is the minimum in the current pool). We keep track of the highest performance value seen during the iteration.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {6        int[][] engineers = new int[n][2];7        for (int i = 0; i < n; i++) {8            engineers[i] = new int[]{efficiency[i], speed[i]};9        }10 11        // Sort engineers by efficiency in descending order12        Arrays.sort(engineers, (a, b) -> b[0] - a[0]);13 14        // Min-heap to maintain the k largest speeds15        PriorityQueue<Integer> speedHeap = new PriorityQueue<>(k, (a, b) -> a - b);16        17        long currentSpeedSum = 0;18        long maxPerformance = 0;19        long MOD = 1_000_000_007;20 21        for (int[] engineer : engineers) {22            int currentEfficiency = engineer[0];23            int currentSpeed = engineer[1];24 25            // Add current engineer's speed to the team26            speedHeap.add(currentSpeed);27            currentSpeedSum += currentSpeed;28 29            // If team size exceeds k, remove the one with the lowest speed30            if (speedHeap.size() > k) {31                currentSpeedSum -= speedHeap.poll();32            }33 34            // Calculate performance with the current team.35            // The minimum efficiency is the current engineer's efficiency36            // because we sorted by efficiency in descending order.37            maxPerformance = Math.max(maxPerformance, currentSpeedSum * currentEfficiency);38        }39 40        return (int) (maxPerformance % MOD);41    }42}

Complexity

Time

O(N log N). Sorting the engineers takes `O(N log N)`. The loop runs `N` times, and each heap operation (add/poll) takes `O(log K)`. So the loop takes `O(N log K)`. The total complexity is dominated by sorting, resulting in `O(N log N)`.

Space

O(N). We use an array of size `N` to store the engineer pairs. The priority queue stores at most `K` elements. So, the space complexity is `O(N + K) = O(N)`.

Trade-offs

Pros

Highly efficient and passes the given constraints.
Optimal solution for this problem.
Clever use of sorting and a priority queue to avoid re-computation.

Cons

The logic is more complex to understand compared to the brute-force approach.
Requires careful handling of data structures (sorting pairs, using a priority queue).

Solutions

Solution

1class Solution {2private3  static final int MOD = (int)1 e9 + 7;4public5  int maxPerformance(int n, int[] speed, int[] efficiency, int k) {6    int[][] t = new int[n][2];7    for (int i = 0; i < n; ++i) {8      t[i] = new int[]{speed[i], efficiency[i]};9    }10    Arrays.sort(t, (a, b)->b[1] - a[1]);11    PriorityQueue<Integer> q = new PriorityQueue<>();12    long tot = 0;13    long ans = 0;14    for (var x : t) {15      int s = x[0], e = x[1];16      tot += s;17      ans = Math.max(ans, tot * e);18      q.offer(s);19      if (q.size() == k) {20        tot -= q.poll();21      }22    }23    return (int)(ans % MOD);24  }25}

1class Solution {2public:3  int maxPerformance(int n, vector<int> &speed, vector<int> &efficiency,4                     int k) {5    vector<pair<int, int>> t(n);6    for (int i = 0; i < n; ++i)7      t[i] = {-efficiency[i], speed[i]};8    sort(t.begin(), t.end());9    priority_queue<int, vector<int>, greater<int>> q;10    long long ans = 0, tot = 0;11    int mod = 1e9 + 7;12    for (auto &x : t) {13      int s = x.second, e = -x.first;14      tot += s;15      ans = max(ans, tot * e);16      q.push(s);17      if (q.size() == k) {18        tot -= q.top();19        q.pop();20      }21    }22    return (int)(ans % mod);23  }24};

1class Solution:2    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int: t = sorted(zip(speed, efficiency), key=lambda x: - x[1]) ans = tot = 0 mod = 10 ** 9 + 7 h = [] for s, e in t: tot += s ans = max(ans, tot * e) heappush(h, s) if len(h) == k: tot -= heappop(h) return ans % mod

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem