LeetCode 1383 - Maximum Performance of a Team

This problem asks us to build a team of at most k engineers such that the team's performance is maximized. Each engineer

leetcodehardarraygreedysortingheap-(priority-queue)

LeetCode Problem 1383

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

This problem asks us to build a team of at most k engineers such that the team's performance is maximized.

Each engineer has two attributes:

  • speed[i], representing how fast the engineer is
  • efficiency[i], representing how efficient the engineer is

The performance of a team is defined as:

$$\text{performance} = (\text{sum of team speeds}) \times (\text{minimum efficiency in the team})$$

This definition is important because the minimum efficiency among all selected engineers becomes the bottleneck for the entire team.

We are allowed to choose any number of engineers from 1 up to k. We do not have to use exactly k engineers.

The input consists of:

  • n, the total number of engineers
  • speed, an array of length n
  • efficiency, another array of length n
  • k, the maximum allowed team size

The output should be the maximum possible performance modulo:

$$10^9 + 7$$

The constraints are very large:

  • n can be up to 100000
  • speeds can be up to 100000
  • efficiencies can be up to 100000000

These limits immediately rule out exponential or quadratic approaches. Any solution significantly worse than O(n log n) will likely time out.

Several edge cases are important:

  • k = 1, where we simply need the single engineer with maximum speed * efficiency
  • k = n, where all engineers are potentially selectable
  • Engineers with extremely high efficiency but low speed
  • Engineers with extremely high speed but low efficiency
  • Cases where the optimal team uses fewer than k engineers
  • Large values that can overflow 32-bit integers, especially in Go

The problem guarantees:

  • speed and efficiency have equal length
  • all values are positive
  • at least one engineer exists

Because all values are positive, adding more speed generally helps, but adding an engineer with low efficiency may dramatically reduce the team's minimum efficiency. Balancing these two competing factors is the key challenge.

Approaches

Brute Force Approach

A brute-force solution would try every possible subset of engineers whose size is at most k.

For each subset:

  1. Compute the sum of speeds
  2. Compute the minimum efficiency
  3. Calculate the performance
  4. Track the maximum result

This works because it directly evaluates every valid team configuration, guaranteeing the optimal answer.

However, the number of subsets is enormous. There are:

$$2^n$$

possible subsets in total. Even restricting subset sizes to at most k does not help enough when n = 100000.

This approach becomes computationally impossible even for moderate values of n.

Optimal Greedy + Heap Approach

The key insight comes from analyzing the formula:

$$(\text{sum of speeds}) \times (\text{minimum efficiency})$$

Suppose we decide that a specific engineer is the minimum-efficiency engineer in the team.

If that engineer determines the minimum efficiency, then every other selected engineer must have efficiency greater than or equal to that engineer's efficiency.

This observation suggests sorting engineers by efficiency in descending order.

When processing engineers from highest efficiency to lowest:

  • The current engineer becomes the minimum efficiency candidate
  • All previously processed engineers have efficiency at least as large
  • Therefore, any team formed from the processed engineers has minimum efficiency equal to the current engineer's efficiency

Now the problem becomes:

For the current minimum efficiency, choose up to k engineers with the largest total speed.

To maximize the speed sum efficiently, we use a min-heap:

  • Keep track of the selected speeds
  • If the team exceeds size k, remove the smallest speed
  • Maintain the running sum of speeds

This gives an efficient O(n log k) solution after sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Enumerates every possible subset
Optimal O(n log n) O(k) Sort by efficiency and maintain best speeds using a heap

Algorithm Walkthrough

  1. Combine each engineer's efficiency and speed into a pair.

We create tuples like:

(efficiency, speed)

This allows us to process both values together. 2. Sort the engineers by efficiency in descending order.

This is the critical greedy step.

When processing engineers from highest efficiency to lowest, the current engineer always becomes the minimum efficiency in the current candidate team. 3. Initialize a min-heap to store selected speeds.

The heap helps us efficiently maintain the k largest speeds encountered so far. 4. Maintain a running sum of speeds.

Each time we add an engineer's speed to the heap, we also add it to the running total. 5. Iterate through the sorted engineers.

For each engineer:

  • Add the engineer's speed to the heap
  • Add the speed to the running sum
  1. If the heap size exceeds k, remove the smallest speed.

Since we only want at most k engineers, we discard the slowest engineer currently in the team.

A min-heap makes this operation efficient. 7. Compute the current performance.

Since the current engineer has the smallest efficiency among all engineers processed so far:

$$\text{performance} = (\text{current speed sum}) \times (\text{current efficiency})$$ 8. Update the maximum performance seen so far. 9. Return the answer modulo 10^9 + 7.

Why it works

The algorithm works because of the sorting order.

At every iteration, the current engineer defines the minimum efficiency of the team. All previously considered engineers have equal or higher efficiency, so adding them cannot reduce the minimum efficiency further.

Therefore, once the minimum efficiency is fixed, the only remaining objective is maximizing the sum of speeds. Keeping the k largest speeds using a heap guarantees the best possible speed sum for that efficiency threshold.

By evaluating every possible minimum efficiency exactly once, the algorithm explores all valid optimal team configurations.

Python Solution

from typing import List
import heapq

class Solution:
    def maxPerformance(
        self,
        n: int,
        speed: List[int],
        efficiency: List[int],
        k: int
    ) -> int:
        MOD = 10**9 + 7

        engineers = sorted(
            zip(efficiency, speed),
            reverse=True
        )

        speed_heap = []
        speed_sum = 0
        max_performance = 0

        for current_efficiency, current_speed in engineers:
            heapq.heappush(speed_heap, current_speed)
            speed_sum += current_speed

            if len(speed_heap) > k:
                removed_speed = heapq.heappop(speed_heap)
                speed_sum -= removed_speed

            performance = speed_sum * current_efficiency
            max_performance = max(max_performance, performance)

        return max_performance % MOD

The implementation begins by pairing efficiencies and speeds together using zip. We then sort the engineers in descending order of efficiency.

The speed_heap stores the selected engineer speeds. Since Python's heapq is a min-heap, the smallest speed is always at the root.

As we iterate through the engineers, we add each engineer's speed to both the heap and the running speed total.

If the heap size exceeds k, we remove the smallest speed. This guarantees that the heap always contains the best possible set of speeds for the current efficiency threshold.

At every iteration, we compute the performance using:

speed_sum * current_efficiency

Because the engineers are processed in descending efficiency order, the current efficiency is guaranteed to be the minimum efficiency in the current team.

Finally, we return the result modulo 10^9 + 7.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

const MOD int = 1e9 + 7

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
	type Engineer struct {
		efficiency int
		speed      int
	}

	engineers := make([]Engineer, n)

	for i := 0; i < n; i++ {
		engineers[i] = Engineer{
			efficiency: efficiency[i],
			speed:      speed[i],
		}
	}

	sort.Slice(engineers, func(i, j int) bool {
		return engineers[i].efficiency > engineers[j].efficiency
	})

	speedHeap := &MinHeap{}
	heap.Init(speedHeap)

	var speedSum int64 = 0
	var maxPerformance int64 = 0

	for _, engineer := range engineers {
		heap.Push(speedHeap, engineer.speed)
		speedSum += int64(engineer.speed)

		if speedHeap.Len() > k {
			removedSpeed := heap.Pop(speedHeap).(int)
			speedSum -= int64(removedSpeed)
		}

		performance := speedSum * int64(engineer.efficiency)

		if performance > maxPerformance {
			maxPerformance = performance
		}
	}

	return int(maxPerformance % int64(MOD))
}

The Go solution follows the same algorithmic structure as the Python version, but Go requires explicit heap implementation using the container/heap package.

A custom MinHeap type implements the required heap interface methods.

One important Go-specific detail is integer overflow. The performance calculation can exceed the range of 32-bit integers, so the implementation uses int64 for:

  • speedSum
  • maxPerformance
  • intermediate multiplication

Without this conversion, overflow bugs would occur on large inputs.

Worked Examples

Example 1

Input:
n = 6
speed = [2,10,3,1,5,8]
efficiency = [5,4,3,9,7,2]
k = 2

First, pair and sort by efficiency descending:

Efficiency Speed
9 1
7 5
5 2
4 10
3 3
2 8

Now process each engineer.

Step Current Engineer Heap Speed Sum Min Efficiency Performance Max
1 (9,1) [1] 1 9 9 9
2 (7,5) [1,5] 6 7 42 42
3 (5,2) [2,5] 7 5 35 42
4 (4,10) [5,10] 15 4 60 60
5 (3,3) [5,10] 15 3 45 60
6 (2,8) [8,10] 18 2 36 60

Final answer:

60

Example 2

Input:
k = 3

Same sorted order.

Step Heap Speed Sum Efficiency Performance Max
1 [1] 1 9 9 9
2 [1,5] 6 7 42 42
3 [1,5,2] 8 5 40 42
4 [2,5,10] 17 4 68 68
5 [3,5,10] 18 3 54 68
6 [5,8,10] 23 2 46 68

Final answer:

68

Example 3

Input:
k = 4

The optimal team eventually achieves:

(2 + 10 + 5 + 1) * 4 = 72

Final answer:

72

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, heap operations are O(log k)
Space O(k) Heap stores at most k speeds

The sorting step requires:

$$O(n \log n)$$

Each engineer is inserted into the heap once and possibly removed once.

Heap operations cost:

$$O(\log k)$$

So total heap cost is:

$$O(n \log k)$$

Since k <= n, the overall complexity remains:

$$O(n \log n)$$

The heap never stores more than k elements, so auxiliary space usage is O(k).

Test Cases

from typing import List

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        import heapq

        MOD = 10**9 + 7

        engineers = sorted(zip(efficiency, speed), reverse=True)

        speed_heap = []
        speed_sum = 0
        answer = 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)

            answer = max(answer, speed_sum * e)

        return answer % MOD

solution = Solution()

assert solution.maxPerformance(
    6,
    [2,10,3,1,5,8],
    [5,4,3,9,7,2],
    2
) == 60  # example 1

assert solution.maxPerformance(
    6,
    [2,10,3,1,5,8],
    [5,4,3,9,7,2],
    3
) == 68  # example 2

assert solution.maxPerformance(
    6,
    [2,10,3,1,5,8],
    [5,4,3,9,7,2],
    4
) == 72  # example 3

assert solution.maxPerformance(
    1,
    [5],
    [10],
    1
) == 50  # single engineer

assert solution.maxPerformance(
    3,
    [2,8,2],
    [2,7,1],
    1
) == 56  # choose best individual engineer

assert solution.maxPerformance(
    3,
    [5,5,5],
    [3,3,3],
    3
) == 45  # all engineers identical

assert solution.maxPerformance(
    5,
    [100000,100000,100000,100000,100000],
    [100000000,100000000,100000000,100000000,100000000],
    5
) == 999999832  # large values and modulo behavior

assert solution.maxPerformance(
    4,
    [10,1,1,1],
    [1,10,10,10],
    2
) == 20  # high efficiency may outweigh raw speed

assert solution.maxPerformance(
    5,
    [1,2,3,4,5],
    [5,4,3,2,1],
    5
) == 15  # optimal team may not use all engineers

assert solution.maxPerformance(
    5,
    [9,8,7,6,5],
    [1,2,3,4,5],
    3
) == 72  # heap replacement behavior
Test Why
Example 1 Validates standard case with k = 2
Example 2 Validates larger team size
Example 3 Confirms optimal team changes with larger k
Single engineer Smallest valid input
k = 1 Ensures single best engineer is chosen
Identical engineers Tests uniform values
Large values Validates modulo and overflow handling
High efficiency vs speed Tests tradeoff behavior
Optimal team smaller than k Confirms algorithm does not force k engineers
Heap replacement behavior Ensures smallest speeds are correctly removed

Edge Cases

One important edge case occurs when k = 1. In this situation, every team contains exactly one engineer, so the performance becomes:

$$\text{speed} \times \text{efficiency}$$

A buggy implementation might still attempt unnecessary heap logic or accidentally combine engineers. The current implementation naturally handles this because the heap size is restricted to one element.

Another important case occurs when the optimal solution uses fewer than k engineers. Since the problem says "at most k", we are not required to fill the team completely. A naive implementation might incorrectly force exactly k engineers into the team, lowering the minimum efficiency unnecessarily. The heap-based solution evaluates performance at every step, so smaller teams are considered automatically.

Large integer overflow is another major concern. Speeds can sum to:

$$100000 \times 100000 = 10^{10}$$

Multiplying again by efficiency can produce values around:

$$10^{18}$$

This exceeds 32-bit integer limits. The Go implementation explicitly uses int64 for all critical arithmetic to avoid overflow bugs.

Another subtle edge case involves removing engineers from the heap. When the heap exceeds size k, we must remove the smallest speed, not the largest. Removing the wrong value would reduce the speed sum unnecessarily and produce incorrect results. Using a min-heap guarantees that the least valuable speed contribution is discarded first.