1383. Maximum Performance of a Team - Solution

Q: 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.

Q: 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 serves the same purpose while maintaining the running speed sum and updating the maximum performance.

The problem

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⁸

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).

Python

import heapq

class Solution:
    def maxPerformance(self, n, speed, efficiency, k):
        engineers = list(zip(efficiency, speed))
        engineers.sort(reverse=True)
        speed_heap = []
        speed_sum = max_perf = 0
        for e, s in engineers:
            heapq.heappush(speed_heap, s)
            speed_sum += s
            if len(speed_heap) > k:
                speed_sum -= heapq.heappop(speed_heap)
            max_perf = max(max_perf, speed_sum * e)
        return max_perf % (10**9 + 7)

Java

import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        long mod = (long)1e9 + 7;
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; i++) {
            engineers[i] = new int[]{efficiency[i], speed[i]};
        }
        Arrays.sort(engineers, (a, b) -> b[0] - a[0]);
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        long speedSum = 0, maxPerformance = 0;
        
        for (int[] engineer : engineers) {
            int currEfficiency = engineer[0];
            int currSpeed = engineer[1];

            if (minHeap.size() >= k) {
                speedSum -= minHeap.poll();
            }

            speedSum += currSpeed;
            minHeap.offer(currSpeed);

            maxPerformance = Math.max(maxPerformance, speedSum * currEfficiency);
        }

        return (int)(maxPerformance % mod);
    }
}

C++

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
    vector<pair<int, int>> engineers(n);
    for (int i = 0; i < n; ++i) {
        engineers[i] = {efficiency[i], speed[i]};
    }
    sort(engineers.rbegin(), engineers.rend());

    priority_queue<int, vector<int>, greater<int>> minHeap;
    long speedSum = 0, maxPerf = 0;
    for (const auto& [e, s] : engineers) {
        minHeap.push(s);
        speedSum += s;
        if (minHeap.size() > k) {
            speedSum -= minHeap.top();
            minHeap.pop();
        }
        maxPerf = max(maxPerf, speedSum * e);
    }
    return maxPerf % 1000000007;
}

JavaScript

const maxPerformance = (n, speed, efficiency, k) => {
    let engineers = [];
    for (let i = 0; i < n; ++i) {
        engineers.push([efficiency[i], speed[i]]);
    }
    engineers.sort((a, b) => b[0] - a[0]);

    let minHeap = [];
    let speedSum = 0, maxPerf = 0, mod = 1e9 + 7;

    for (const [eff, spd] of engineers) {
        if (minHeap.length === k) {
            speedSum -= minHeap.pop();
            minHeap = minHeap.sort((a, b) => a - b);
        }
        speedSum += spd;
        minHeap.push(spd);

        let perf = speedSum * eff;
        maxPerf = Math.max(maxPerf, perf);
    }

    return maxPerf % mod;
};

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int comparator(const void *a, const void *b) {
    return ((int*)b)[1] - ((int*)a)[1];
}

int maxPerformance(int n, int* speed, int speedSize, int* efficiency, int efficiencySize, int k) {
    int MOD = 1000000007;
    int engineers[n][2];
    for (int i = 0; i < n; i++) {
        engineers[i][0] = speed[i];
        engineers[i][1] = efficiency[i];
    }
    qsort(engineers, n, sizeof(engineers[0]), comparator);

    int *minHeap = malloc(k * sizeof(int));
    int heapSize = 0, topKSpeedSum = 0, maxPerformance = 0;

    for (int i = 0; i < n; i++) {
        int currSpeed = engineers[i][0];
        int currEfficiency = engineers[i][1];
        if (heapSize < k) {
            minHeap[heapSize++] = currSpeed;
            topKSpeedSum += currSpeed;
        } else if (currSpeed > minHeap[0]) {
            topKSpeedSum += currSpeed - minHeap[0];
        } else {
            currEfficiency = 0;
        }

        for (int j = heapSize / 2 - 1; j >= 0; j--) {
            int minPos = j;
            if (2*j + 1 < heapSize && minHeap[2*j + 1] < minHeap[minPos]) {
                minPos = 2*j + 1;
            }
            if (2*j + 2 < heapSize && minHeap[2*j + 2] < minHeap[minPos]) {
                minPos = 2*j + 2;
            }
            if (minPos != j) {
                int tmp = minHeap[j];
                minHeap[j] = minHeap[minPos];
                minHeap[minPos] = tmp;
            }
        }
        
        if (heapSize < k) {
            minHeap[heapSize++] = currSpeed;
        } else if (currSpeed > minHeap[0]) {
            topKSpeedSum += currSpeed - minHeap[0];
            minHeap[0] = currSpeed;
        }

        maxPerformance = (int)(((long long)topKSpeedSum * currEfficiency) % MOD > maxPerformance ?
            ((long long)topKSpeedSum * currEfficiency) % MOD : maxPerformance);
    }
    free(minHeap);
    return maxPerformance;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxPerformance(int n, int[] speed, int[] efficiency, int k) {
        var engineers = new List<(int eff, int spd)>();
        for (int i = 0; i < n; i++) {
            engineers.Add((efficiency[i], speed[i]));
        }
        engineers.Sort((a, b) => b.eff.CompareTo(a.eff));

        var minHeap = new SortedSet<(int speed, int idx)>();
        long speedSum = 0, maxPerf = 0;
        int mod = 1000000007;

        foreach (var engineer in engineers) {
            speedSum += engineer.spd;
            minHeap.Add((engineer.spd, engineers.IndexOf(engineer)));

            if (minHeap.Count > k) {
                speedSum -= minHeap.Min.speed;
                minHeap.Remove(minHeap.Min);
            }

            maxPerf = Math.Max(maxPerf, speedSum * engineer.eff);
        }

        return (int)(maxPerf % mod);
    }
}

This solution utilizes Python's heapq as a min-heap structure to efficiently handle and minimize the smallest elements when necessary. Engineers are sorted by efficiency, and possible teams are evaluated based on the current efficiency and speed set maintained in the heap.

Complexity

Time Complexity: O(n log n) due to sorting and min-heap insertion and removal.

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

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.

Python

class Solution:
    def maxPerformance(self, n, speed, efficiency, k):
        # Binary Search and DP for detailed analysis
        return 0  # Placeholder Implementation

Java

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        // Implement a sketch of DP with Binary Search Approach
        return 0; // Placeholder while retaining constraints
    }
}

C++

#include <vector>
#include <algorithm>

using namespace std;

long maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
    // DP + Binary Search Intuitive Approach for Educational Purposes
    return 0; // Placeholder Implementation
}

JavaScript

const maxPerformance = (n, speed, efficiency, k) => {
    // An overview of Binary Search with DP lists
    return 0; // Placeholder Solution
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int compare(const void *a, const void *b) {
    return ((int*)b)[1] - ((int*)a)[1];
}

long maxPerformance(int n, int* speed, int speedSize, int* efficiency, int efficiencySize, int k) {
    // Implement using DP and Binary Search approach
    return 0; // Placeholder Implementation
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxPerformance(int n, int[] speed, int[] efficiency, int k) {
        // Outline of DP + Binary Search
        return 0; // Placeholder Implementation
    }
}

Given that Python allows direct use of lists and integrated functional transformations, a DP approach dealing with combinations of speeds and efficiency might leverage Python's flexible list ordering while identifying optimal top speeds.

Complexity

Time Complexity: O(n^2 log n) derived from extensive state transitions.

Space Complexity: O(n) for accumulating possible results.

Try this approach in the editor

Approach 3: Default Approach

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
	t := make([][]int, n)
	for i, s := range speed {
		t[i] = []int{s, efficiency[i]}
	}
	sort.Slice(t, func(i, j int) bool { return t[i][1] > t[j][1] })
	var mod int = 1e9 + 7
	ans, tot := 0, 0
	pq := hp{}
	for _, x := range t {
		s, e := x[0], x[1]
		tot += s
		ans = max(ans, tot*e)
		heap.Push(&pq, s)
		if pq.Len() == k {
			tot -= heap.Pop(&pq).(int)
		}
	}
	return ans % mod
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy with Min-Heap for Speed	Time Complexity: O(n log n) due to sorting and min-heap insertion and removal. Space Complexity: O(k) for the additional min-heap storage.
Dynamic Programming (DP) with Binary Search	Time Complexity: O(n^2 log n) derived from extensive state transitions. Space Complexity: O(n) for accumulating possible results.
Default Approach	–

Approach

Complexity

Greedy with Min-Heap for Speed

Time Complexity: O(n log n) due to sorting and min-heap insertion and removal.

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

Dynamic Programming (DP) with Binary Search

Time Complexity: O(n^2 log n) derived from extensive state transitions.

Space Complexity: O(n) for accumulating possible results.

Default Approach

–

Complexity analysis

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

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.

Maximum Performance of a Team solution and explanation

The problem

Approach overview

Approach 1: Greedy with Min-Heap for Speed

Approach 2: Dynamic Programming (DP) with Binary Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Performance of a Team solution and explanation

The problem

Approach overview

Approach 1: Greedy with Min-Heap for Speed

Approach 2: Dynamic Programming (DP) with Binary Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems