Skip to main content
Talentd

Maximum Performance of a Team - Solution & Explanation

HardArrayGreedySortingHeap (Priority Queue)16 min readAsked at: Amazon, Google, PhonePe +4
Practice this problem

Problem Statement

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 ith 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 109 + 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 <= 105
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 105
  • 1 <= efficiency[i] <= 108

Approach Overview

Problem Overview: You are given two arrays representing the speed and efficiency of engineers. Select at most k engineers such that the team's performance, defined as (sum of speeds) * (minimum efficiency), is maximized. The challenge comes from the fact that adding a faster engineer may reduce the minimum efficiency of the team.

Approach 1: Brute Force Team Enumeration (Exponential Time)

The most straightforward idea is to try every possible subset of engineers of size up to k. For each subset, compute the total speed and find the minimum efficiency, then calculate performance. This requires generating combinations and evaluating each one. The time complexity grows exponentially, roughly O(C(n, k) * k), and the space complexity is O(k) for subset tracking. This approach quickly becomes infeasible when n grows beyond small limits, but it helps clarify the relationship between speed sum and minimum efficiency.

Approach 2: Dynamic Programming with Binary Search (O(n log n + nk))

Another idea uses dynamic programming combined with sorting. First, sort engineers by efficiency in descending order using sorting. When efficiency is fixed at position i, it acts as the minimum efficiency of the team. You then choose up to k-1 engineers from earlier elements that maximize the speed sum. A DP structure or maintained ordered set with binary search can help track candidate speed sums. The time complexity is about O(n log n + nk) depending on implementation, and space complexity is O(n). This method demonstrates the core insight that efficiency should be treated as the limiting factor.

Approach 3: Greedy with Min-Heap for Speed (Optimal) (O(n log k))

The optimal solution uses a greedy strategy with a heap (priority queue). First, pair each engineer's efficiency and speed, then sort engineers by efficiency in descending order. When processing engineer i, treat their efficiency as the minimum efficiency of the team. Maintain a running sum of speeds for the current team. Use a min-heap to keep the fastest k engineers seen so far: push the current speed, and if the heap size exceeds k, remove the smallest speed. This ensures the team always keeps the largest speed sum possible while the current efficiency acts as the bottleneck. At each step, compute performance = speedSum * currentEfficiency and update the maximum.

This greedy insight works because the minimum efficiency always comes from the engineer with the lowest efficiency in the selected group. By iterating efficiencies in descending order, that value becomes fixed for the current iteration, allowing you to focus on maximizing the speed sum using a heap. The algorithm runs in O(n log k) time due to heap operations and O(k) space.

Recommended for interviews: The greedy + min-heap solution is what interviewers expect. It demonstrates understanding of greedy algorithms, efficient data structures, and the ability to transform a complex objective into a sorted traversal problem. Mentioning the brute force idea shows reasoning, but implementing the heap-based solution proves strong algorithmic skill.

Approach 1: Greedy with Min-Heap for Speed

This approach involves sorting engineers by their efficiency in descending order, ensuring that each team's minimum efficiency is dominated by its highest-efficiency member being considered rather than doing a costly check of all members.

After this, we use a min-heap to keep track of the top 'k' speeds. The strategy is to iterate through each engineer (sorted by efficiency), compute potential team performance by inserting their speed into the speed sum (if advantageous), and then multiplying by the current engineer's efficiency (the smallest efficiency thus far in the sorted order).

We first convert each engineer's data into a tuple of speed and efficiency, after which we sort the engineers by efficiency. A min-heap helps keep only the fastest speeds currently deemed many enough to be an optimal team.

Each iteration over the engineers allows us to compute and maintain what the performance of the top engineers (by speed) looks like under the current efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting and heap operations.

Space Complexity: O(k) for maintaining the min-heap.

Try this approach in the editor →

Approach 2: Dynamic Programming (DP) with Binary Search

Instead of using a heap, an alternative approach employs dynamic programming. For each engineer sorted by efficiency, we determine the maximum performance we can achieve using a binary search to find an optimal combination in an accumulated list of maximum speeds and efficiencies.

This involves recursively filling up a DP table with potential performance values, achieving optimization through binary search.

Due to complexity, a full DP + binary search approach has intricate implementation specific details. A similar illustrative solution in pseudocode involves maintaining an array where calculating potential top speeds and efficiencies are iterated and evaluated using a DP-based recurrence relation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 log n) in a worst-case naive implementation.

Space Complexity: O(n) for the DP table.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy with Min-Heap for Speed

Time Complexity: O(n log n) due to sorting and heap operations.

Space Complexity: O(k) for maintaining the min-heap.

Dynamic Programming (DP) with Binary Search

Time Complexity: O(n^2 log n) in a worst-case naive implementation.

Space Complexity: O(n) for the DP table.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset EnumerationO(C(n,k) * k)O(k)Conceptual understanding or very small input sizes
Dynamic Programming with Binary SearchO(n log n + nk)O(n)Exploring structured optimizations after sorting by efficiency
Greedy with Min-Heap for SpeedO(n log k)O(k)Optimal solution for large inputs and typical interview expectations

Video Solution

Maximum Performance of a Team - Leetcode 1383 - Python • NeetCode • 36,630 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Performance of a Team easy or hard?
Maximum Performance of a Team is classified as a hard problem on LeetCode. The difficulty comes from combining greedy reasoning, sorting by efficiency, and maintaining the optimal speed set with a heap while respecting the team size constraint.
Maximum Performance of a Team Python/Java solution
Python and Java implementations typically use a priority queue or heap structure. In Python, the heapq module provides the min-heap used to track speeds. In Java, PriorityQueue<Integer> serves the same purpose while maintaining the running speed sum and updating the maximum performance.
How to solve Maximum Performance of a Team in O(n log k)?
First pair each engineer's efficiency with their speed and sort engineers by efficiency in descending order. Maintain a running sum of speeds and a min-heap storing the current team speeds. If the heap size exceeds k, remove the smallest speed. After each insertion, compute performance as speedSum multiplied by the current efficiency and track the maximum.
What is the best approach for Maximum Performance of a Team?
The most efficient approach uses a greedy strategy with a min-heap. Engineers are sorted by efficiency in descending order so the current engineer defines the minimum efficiency of the team. A min-heap keeps track of the k highest speeds while maintaining the running speed sum. This method runs in O(n log k) time and is considered the optimal solution.
Is Maximum Performance of a Team asked at Google/Amazon/Meta?
Maximum Performance of a Team is a classic hard interview problem involving greedy algorithms and heaps. Variants of this problem have appeared in interviews at companies such as Amazon, Google, and Meta because it tests sorting strategy, priority queue usage, and optimization reasoning.
What data structure is used in Maximum Performance of a Team?
The key data structure is a min-heap (priority queue). It efficiently maintains the k largest speeds while processing engineers sorted by efficiency. Sorting is also required to process candidates in decreasing efficiency order.
What is the time complexity of Maximum Performance of a Team?
The optimal greedy solution runs in O(n log k) time. Sorting engineers by efficiency takes O(n log n), and each heap insertion or removal costs O(log k). Since every engineer is processed once, the overall complexity is dominated by heap operations.

Ready to solve this problem?

Practice Maximum Performance of a Team with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Fruits Harvested After at Most K Steps