Skip to main content

Heaps

Maximum Performance of a Team Solution In C++/Python/Java/JS

Problem Description

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

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.


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.

Constraints

  • 1 <= k <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
💡
Try it Yourself First
Sort engineers by efficiency and use a min heap to track the top k speeds. Update the sum dynamically and compute the maximum performance in a single pass.

Brute Force Approach

Intuition

Our goal is to maximize the team's performance by selecting up to k engineers while ensuring that the minimum efficiency among them determines the overall score. To achieve this, we must explore all possible combinations of k engineers and determine the maximum possible product of their total speed and the smallest efficiency in the group.

We start by pairing each engineer’s speed with their corresponding efficiency, treating efficiency as a constraint that affects the final score. The challenge is to find a subset of k engineers that maximizes the sum of selected speeds while keeping the minimum efficiency in the subset as large as possible.

To systematically explore all valid subsets, we use a recursive approach to generate all possible combinations. At each step, we either include the current engineer in the subset or skip them, then move to the next index. When exactly k engineers are selected, we compute the performance by multiplying the sum of selected speeds by the minimum efficiency in the subset and update the global maximum if necessary.

By iterating through all possible subsets, we ensure that no optimal selection is missed. However, this brute-force approach becomes computationally expensive as n grows, since generating and evaluating all combinations leads to exponential time complexity. While it guarantees the correct result, it is not efficient for large inputs.

Approach

Step 1: Store Engineer Indices

  • Store indices of engineers from 0 to n-1 in a list to track all available engineers.

Step 2: Iterate Over Possible Team Sizes

  • Try all possible team sizes from 1 to k since we can select at most k engineers.

Step 3: Generate Engineer Combinations Recursively

  • Use recursion to generate all possible selections of engineers for the current team size.
  • At each step, either include the current engineer or skip to the next one.

Step 4: Compute Performance for Selected Engineers

  • When exactly the required number of engineers are selected, calculate the performance.
  • Compute the total speed by summing up selected engineers’ speeds.
  • Find the minimum efficiency among selected engineers.
  • Multiply the total speed with the minimum efficiency to get the performance.

Step 5: Update the Maximum Performance

  • Compare the newly computed performance with the global maximum and update if it’s higher.

Step 6: Return the Maximum Performance

  • After all possible team selections are explored, return the highest recorded performance modulo 10^9 + 7.

Dry Run

Input:

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

Step 1: Store Engineer Indices

  • Store indices of engineers:
  • indices = [0, 1, 2, 3, 4, 5]

Step 2: Generate Combinations Recursively

  • Find all combinations of up to 2 engineers (since k = 2) and compute the maximum performance.

Step 3: Exploring Combinations

Choose 1 Engineer (Engineer 1):

  • Sum of speeds = 2
  • Efficiency = 5
  • Performance = 2 × 5 = 10

Choose 1 Engineer (Engineer 2):

  • Sum of speeds = 10
  • Efficiency = 4
  • Performance = 10 × 4 = 40

Choose 1 Engineer (Engineer 3):

  • Sum of speeds = 3
  • Efficiency = 3
  • Performance = 3 × 3 = 9

Choose 1 Engineer (Engineer 4):

  • Sum of speeds = 1
  • Efficiency = 9
  • Performance = 1 × 9 = 9

Choose 1 Engineer (Engineer 5):

  • Sum of speeds = 5
  • Efficiency = 7
  • Performance = 5 × 7 = 35

Choose 1 Engineer (Engineer 6):

  • Sum of speeds = 8
  • Efficiency = 2
  • Performance = 8 × 2 = 16

Now, choosing 2 engineers:

Choose Engineer 1 (speed = 2, efficiency = 5) and Engineer 2 (speed = 10, efficiency = 4):

  • Sum of speeds = 2 + 10 = 12
  • Minimum efficiency = min(5,4) = 4
  • Performance = 12 × 4 = 48

Choose Engineer 1 and Engineer 3 (speed = 3, efficiency = 3):

  • Sum of speeds = 2 + 3 = 5
  • Minimum efficiency = min(5,3) = 3
  • Performance = 5 × 3 = 15

Choose Engineer 1 and Engineer 4 (speed = 1, efficiency = 9):

  • Sum of speeds = 2 + 1 = 3
  • Minimum efficiency = min(5,9) = 5
  • Performance = 3 × 5 = 15

Choose Engineer 1 and Engineer 5:

  • Sum of speeds = 2 + 5 = 7
  • Minimum efficiency = min(5,7) = 5
  • Performance = 7 × 5 = 35

Choose Engineer 2 and Engineer 5:

  • Sum of speeds = 10 + 5 = 15
  • Minimum efficiency = min(4,7) = 4
  • Performance = 15 × 4 = 60 (maximum so far)

Other combinations have lower performance than 60.

Step 4: Compute Final Maximum Performance

  • The highest computed performance is 60.

Final Output: 60

Code for All Languages
C++ 
// Approach: Sorting with Recursive Combinations  
// Language: C++  

class Solution {
public:
    // Function to find the maximum performance of a team by selecting at most k engineers
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        const int MOD = 1e9 + 7;
        long long maxPerf = 0;
        
        // Step 1: Create vector to store indices from 0 to n-1
        vector<int> indices(n);
        for(int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // Step 2: Try all possible combinations of size 1 to k
        for(int size = 1; size <= k; size++) {
            // Generate all combinations of 'size' engineers
            generateCombinations(indices, 0, size, {}, speed, efficiency, maxPerf);
        }
        
        // Step 3: Return the maximum performance modulo 10^9 + 7
        return maxPerf % MOD;
    }
    
private:
    // Helper function to generate all possible combinations of engineers
    void generateCombinations(vector<int>& indices, int start, int size, 
                            vector<int> current, vector<int>& speed, 
                            vector<int>& efficiency, long long& maxPerf) {
        // Step 4: If we have selected required number of engineers
        if(current.size() == size) {
            // Calculate performance for current combination
            long long totalSpeed = 0;
            int minEfficiency = INT_MAX;
            
            for(int idx : current) {
                totalSpeed += speed[idx];
                minEfficiency = min(minEfficiency, efficiency[idx]);
            }
            
            long long perf = totalSpeed * minEfficiency;
            maxPerf = max(maxPerf, perf);
            return;
        }
        
        // Step 5: If we don't have enough elements left
        if(start >= indices.size()) return;
        
        // Step 6: For each position, make recursive choices
        // Choice 1: Include current engineer
        current.push_back(indices[start]);
        generateCombinations(indices, start + 1, size, current, speed, efficiency, maxPerf);
        current.pop_back();
        
        // Choice 2: Don't include current engineer
        generateCombinations(indices, start + 1, size, current, speed, efficiency, maxPerf);
    }
};

Java 
// Approach: Maximum Performance of a Team by Selecting Engineers
// Language: Java

import java.util.*;

class Solution {
    // Function to find the maximum performance of a team by selecting at most k engineers

    // Make maxPerf a class member variable
    private long maxPerf = 0;  
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        final int MOD = 1000000007;
        
        // Step 1: Create an array to store indices from 0 to n-1
        int[] indices = new int[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // Step 2: Try all possible combinations of size 1 to k
        for (int size = 1; size <= k; size++) {
            // Generate all combinations of 'size' engineers
            generateCombinations(indices, 0, size, new ArrayList<>(), speed, efficiency);
        }
        
        // Step 3: Return the maximum performance modulo 10^9 + 7
        return (int) (maxPerf % MOD);
    }
    
    private void generateCombinations(int[] indices, int start, int size,
                                    List<Integer> current, int[] speed,
                                    int[] efficiency) {
        // Step 4: If we have selected the required number of engineers
        if (current.size() == size) {
            // Calculate performance for the current combination
            long totalSpeed = 0;
            int minEfficiency = Integer.MAX_VALUE;
            
            for (int idx : current) {
                totalSpeed += speed[idx];
                minEfficiency = Math.min(minEfficiency, efficiency[idx]);
            }
            
            long perf = totalSpeed * minEfficiency;
            maxPerf = Math.max(maxPerf, perf);
            return;
        }
        
        // Step 5: If we don't have enough elements left
        if (start >= indices.length) return;
        
        // Step 6: For each position, make recursive choices
        // Choice 1: Include current engineer
        current.add(indices[start]);
        generateCombinations(indices, start + 1, size, current, speed, efficiency);
        current.remove(current.size() - 1);
        
        // Choice 2: Don't include current engineer
        generateCombinations(indices, start + 1, size, current, speed, efficiency);
    }
}

Python 
# Approach: Sorting with Recursive Combinations
# Language: Python

from itertools import combinations

class Solution(object):
    # Function to compute the maximum performance using sorting and recursive combinations
    def maxPerformance(self, n, speed, efficiency, k):
        """
        :type n: int
        :type speed: List[int]
        :type efficiency: List[int]
        :type k: int
        :rtype: int
        """
        # Step 1: Create pairs (efficiency[i], speed[i]) and sort by efficiency in descending order
        pairs = sorted(zip(efficiency, speed), reverse=True)
        max_perf = 0
        
        # Step 2: Generate all k-combinations and find the maximum performance
        for combination in combinations(pairs, k):
            # Sum of selected speed values
            sum_speed = sum(speed for _, speed in combination)  
            # Minimum efficiency value in selected pairs
            min_efficiency = min(eff for eff, _ in combination)  
            # Compute max performance
            max_perf = max(max_perf, sum_speed * min_efficiency)  
        
        # Step 3: Return the maximum possible performance modulo 10^9 + 7
        return max_perf % 1000000007

Javascript 
/**
 * Approach: Sorting with Recursive Combinations
 * Language: JavaScript
 *
 * @param {number} n - Number of engineers.
 * @param {number[]} speed - Array representing speed of engineers.
 * @param {number[]} efficiency - Array representing efficiency of engineers.
 * @param {number} k - Maximum number of engineers to select.
 * @return {number} - Maximum possible performance.
 */
var maxPerformance = function(n, speed, efficiency, k) {
    const MOD = 1e9 + 7;
    let maxPerf = 0;
    
    // Step 1: Store elements as (efficiency[i], speed[i]) pairs
    let engineers = [];
    for (let i = 0; i < n; i++) {
        engineers.push([efficiency[i], speed[i]]);
    }
    
    // Step 2: Sort engineers by efficiency in descending order
    engineers.sort((a, b) => b[0] - a[0]);
    
    // Step 3: Generate all k-combinations and find the maximum performance
    const generateCombinations = (start, selected, currSpeedSum) => {
        if (selected.length === k) {
            let minEfficiency = Math.min(...selected.map(idx => engineers[idx][0]));
            maxPerf = Math.max(maxPerf, currSpeedSum * minEfficiency);
            return;
        }

        for (let i = start; i < engineers.length; i++) {
            selected.push(i);
            generateCombinations(i + 1, selected, currSpeedSum + engineers[i][1]);
            selected.pop();
        }
    };
    
    generateCombinations(0, [], 0);
    
    // Step 4: Return the maximum possible performance modulo 10^9 + 7
    return maxPerf % MOD;
};

Time Complexity Analysis: O(n * 2^k)

Sorting the Engineers (O(n log n))

  • We sort the engineers based on efficiency values in descending order to prioritize selection.
  • Sorting takes O(n log n) time.

Generating Combinations Recursively (O(n choose k))

  • The recursive function explores all possible ways to choose at most k engineers from n, which takes O(n choose k) time.
  • In the worst case, this is O(n^k), but practically, it's closer to O(2^k * n) due to backtracking optimizations.

Calculating the Score for Each Combination (O(k))

  • For each valid combination, we compute the sum of selected engineers' speeds and find the minimum efficiency, both taking O(k) time

Final Time Complexity: O(n log n) + O(n choose k * k) ≈ O(n * 2^k)

Space Complexity Analysis: O(n + k)

Sorting and Storage (O(n))

  • We store pairs of (efficiency[i], speed[i]), requiring O(n) space.

Recursive Call Stack (O(k))

  • The recursive function generateCombinations goes at most k levels deep, using O(k) space for function calls and storing selected indices.

Auxiliary Space (O(n))

  • We use an array selected of size O(k) to track combinations. The engineers array takes O(n) space.

Final Space Complexity: O(n)+O(k)=O(n+k)

Why is the Brute Force Approach Computationally Expensive? (TLE Issue)

Exponential Growth Due to Combinations

  • The problem requires selecting at most k engineers out of n, leading to O(n choose k) = O(n! / (k!(n-k)!)) possible groups.
  • Since k can be as large as n (up to 100,000), the worst-case number of selections grows exponentially, making the approach infeasible.

Why Does This Cause TLE?

  • Even for moderate values of k (e.g., 20 or 30), the number of possible selections skyrockets into billions or trillions.
  • Given that speed[i] and efficiency[i] can be large (10⁵ and 10⁸ respectively), each calculation involves large multiplications.
  • This far exceeds the standard computational limit of 10⁸ operations per second, making brute force impractical for large inputs.
The brute-force approach used recursive combinations, leading to exponential time complexity.To optimize, we use a Greedy + Min Heap strategy. Sorting engineers by efficiency ensures we process higher efficiency first. A min heap maintains the top k speeds, dynamically updating the selection. Instead of recomputing sums for every combination, we efficiently update totalSpeed in a single pass.This reduces the time complexity to O(n log n), making the solution much faster.

Optimal Approach

Intuition

The initial approach used recursive combinations to generate all possible selections, leading to an exponential time complexity, making it infeasible for large inputs. To optimize, we adopt a greedy strategy combined with a min heap (priority queue) to dynamically maintain the top k speeds.

By sorting engineers in descending order of efficiency, we ensure that we always process the most efficient engineers first. Since performance depends on the minimum efficiency in the selected group, this guarantees that every selection maintains the highest possible efficiency at that step.

We maintain a running sum of the top k speeds and use a min heap to track the smallest speed in the selection. This allows us to efficiently remove the slowest engineer whenever we exceed k engineers.

Instead of recomputing the sum for every combination, we iteratively update the total speed by adding a new engineer and removing the slowest one when necessary. This ensures that we always maintain the best k engineers, maximizing the overall performance. By multiplying the current speed sum with the current efficiency, we compute the best possible performance dynamically in a single pass.

Approach

Step 1: Create Pairs and Sort by Efficiency

  • Construct pairs (efficiency[i], speed[i]) and sort them in descending order by efficiency.

Step 2: Initialize Min Heap and Variables

  • Use a min heap to track the top k speeds dynamically.
  • Initialize totalSpeed = 0 to store the sum of selected speeds.
  • Initialize maxPerf = 0 to store the maximum performance.

Step 3: Iterate Over Sorted Pairs

  • For each engineer (efficiency, speed):
    • Add speed to totalSpeed and push it into the min heap.
    • If the heap size exceeds k, remove the smallest speed from the heap and update totalSpeed.
    • Calculate performance for all possible team sizes (including k = 1, 2, ..., k).
    • Update maxPerf with the maximum encountered.

Step 4: Return the Result

  • The final maxPerf holds the maximum possible performance for any valid team size (from 1 to k)
  • Return maxPerf % (10^9 + 7).

Dry Run

Input:

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

Step 1: Pair and Sort Elements

  • Pair elements from efficiency with corresponding speed:
  • pairs = [(5,2), (4,10), (3,3), (9,1), (7,5), (2,8)]
  • Sort pairs by efficiency in descending order:
  • sorted_pairs = [(9,1), (7,5), (5,2), (4,10), (3,3), (2,8)]

Step 2: Initialize Min Heap and Variables

  • Min Heap: minHeap = [] (to track the top k speeds)
  • Total Speed: totalSpeed = 0
  • Maximum Performance: maxPerf = 0

Step 3: Iterate Over Sorted Pairs

Iteration 1: Process (9,1)

  • Add 1 to minHeap: [1]
  • Update totalSpeed = 1
  • Heap size < k, so no score calculation yet.

Iteration 2: Process (7,5)

  • Add 5 to minHeap: [1, 5]
  • Update totalSpeed = 1 + 5 = 6
  • Heap size < k, so no score calculation yet.

Iteration 3: Process (5,2)

  • Add 2 to minHeap: [1, 5, 2]
  • Update totalSpeed = 6 + 2 = 8
  • Heap size = k, compute score:
  • Score = 8 × 5 = 40
  • Update maxPerf = 40

Iteration 4: Process (4,10)

  • Add 10 to minHeap: [1, 5, 2, 10]
  • Update totalSpeed = 8 + 10 = 18
  • Heap size exceeds k, remove smallest (1):
  • minHeap = [2, 5, 10]
  • totalSpeed = 18 - 1 = 17
  • Compute score:
  • Score = 17 × 4 = 68
  • Update maxPerf = 68

Iteration 5: Process (3,3)

  • Add 3 to minHeap: [2, 3, 10, 5]
  • Update totalSpeed = 17 + 3 = 20
  • Heap size exceeds k, remove smallest (2):
  • minHeap = [3, 5, 10]
  • totalSpeed = 20 - 2 = 18
  • Compute score:
  • Score = 18 × 3 = 54 (No update, 68 is max).

Iteration 6: Process (2,8)

  • Add 8 to minHeap: [3, 5, 10, 8]
  • Update totalSpeed = 18 + 8 = 26
  • Heap size exceeds k, remove smallest (3):
  • minHeap = [5, 8, 10]
  • totalSpeed = 26 - 3 = 23
  • Compute score:
  • Score = 23 × 2 = 46 (No update, 68 is max).

Step 4: Compute Final Maximum Score

  • The highest score encountered is 68.

Final Output: 68

Code for All Languages
C++ 
// Approach: Greedy Algorithm with Min Heap (Priority Queue) with Sorting
// Language: C++

class Solution {
public:
    // Function to find the maximum performance of a team by selecting at most k engineers
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        const int MOD = 1e9 + 7;
        
        // Step 1: Create pairs of efficiency and speed
        vector<pair<int, int>> engineers;
        for(int i = 0; i < n; i++) {
            engineers.push_back({efficiency[i], speed[i]});
        }
        
        // Step 2: Sort engineers by efficiency in descending order
        sort(engineers.rbegin(), engineers.rend());
        
        // Step 3: Create min heap to maintain k fastest engineers
        priority_queue<int, vector<int>, greater<int>> minHeap;
        long long totalSpeed = 0;
        long long maxPerf = 0;
        
        // Step 4: Process engineers in order of decreasing efficiency
        for(auto [eff, spd] : engineers) {
            // Add current engineer's speed to total
            totalSpeed += spd;
            minHeap.push(spd);
            
            // Step 5: If team size exceeds k, remove slowest engineer
            if(minHeap.size() > k) {
                totalSpeed -= minHeap.top();
                minHeap.pop();
            }
            
            // Step 6: Calculate current performance
            // Current efficiency is minimum as we process in descending order
            maxPerf = max(maxPerf, totalSpeed * eff);
        }
        
        // Step 7: Return the maximum performance modulo 10^9 + 7
        return maxPerf % MOD;
    }
};

Java 
// Approach: Greedy Algorithm with Min Heap (Priority Queue) and Sorting
// Language: Java

import java.util.*;

class Solution {
    // Function to find the maximum performance of a team by selecting at most k engineers
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        final int MOD = 1_000_000_007;
        
        // Step 1: Pair efficiency and speed of engineers
        List<int[]> engineers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            engineers.add(new int[]{efficiency[i], speed[i]});
        }
        
        // Step 2: Sort engineers by efficiency in descending order
        engineers.sort((a, b) -> Integer.compare(b[0], a[0]));
        
        // Step 3: Initialize Min Heap and Performance Variables
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Min Heap to track top k speeds
        long totalSpeed = 0; // Sum of selected speeds
        long maxPerf = 0; // Maximum performance
        
        // Step 4: Process each engineer in sorted order
        for (int[] engineer : engineers) {
            int eff = engineer[0], spd = engineer[1];
            
            // Add current engineer's speed to total
            totalSpeed += spd;
            minHeap.add(spd);
            
            // Step 5: Maintain at most k engineers in the team
            if (minHeap.size() > k) {
                totalSpeed -= minHeap.poll(); // Remove the engineer with the smallest speed
            }
            
            // Step 6: Calculate performance with the current team
            maxPerf = Math.max(maxPerf, totalSpeed * eff);
        }
        
        // Step 7: Return the maximum performance modulo 10^9 + 7
        return (int) (maxPerf % MOD);
    }
}

Python 
# Approach: Greedy Algorithm with Min Heap (Priority Queue) and Sorting
# Language: Python

import heapq

class Solution:
    # Function to find the maximum performance of a team by selecting at most k engineers
    def maxPerformance(self, n, speed, efficiency, k):
        """
        :type n: int
        :type speed: List[int]
        :type efficiency: List[int]
        :type k: int
        :rtype: int
        """
        MOD = 10**9 + 7
        
        # Step 1: Create a list of tuples (efficiency[i], speed[i]) for sorting
        engineers = [(efficiency[i], speed[i]) for i in range(n)]

        # Step 2: Sort the engineers in descending order based on efficiency
        engineers.sort(reverse=True, key=lambda x: x[0])

        # Step 3: Initialize a min heap to track the smallest k speeds
        min_heap = []
        total_speed = 0
        max_perf = 0

        # Step 4: Iterate through sorted engineers
        for eff, spd in engineers:
            # Add speed to total and push into min heap
            total_speed += spd
            heapq.heappush(min_heap, spd)

            # Step 5: Maintain at most k engineers in the team
            if len(min_heap) > k:
                total_speed -= heapq.heappop(min_heap)  # Remove slowest engineer
            
            # Step 6: Compute performance with current team
            max_perf = max(max_perf, total_speed * eff)

        # Step 7: Return the maximum performance modulo 10^9 + 7
        return max_perf % MOD

Javascript 
/**
 * Approach: Greedy Algorithm with Min Heap (Priority Queue) and Sorting
 * Language: JavaScript
 *
 * @param {number} n - Number of engineers.
 * @param {number[]} speed - Array representing speed of engineers.
 * @param {number[]} efficiency - Array representing efficiency of engineers.
 * @param {number} k - Maximum number of engineers to select.
 * @return {number} - Maximum possible performance.
 */
var maxPerformance = function(n, speed, efficiency, k) {
    const MOD = 1e9 + 7;
    
    // Step 1: Store elements as (efficiency[i], speed[i]) pairs
    let engineers = [];
    for (let i = 0; i < n; i++) {
        engineers.push([efficiency[i], speed[i]]);
    }
    
    // Step 2: Sort engineers by efficiency in descending order
    engineers.sort((a, b) => b[0] - a[0]);
    
    // Step 3: Initialize Min Heap and Performance Variables
    let minHeap = []; // Min Heap to track top k speeds
    let totalSpeed = 0; // Sum of selected speeds
    let maxPerf = 0; // Maximum performance

    // Step 4: Process each engineer in sorted order
    for (let [eff, spd] of engineers) {
        // Add current engineer's speed to total
        totalSpeed += spd;
        minHeap.push(spd);
        minHeap.sort((a, b) => a - b); // Maintain min heap property

        // Step 5: Maintain at most k engineers in the team
        if (minHeap.length > k) {
            totalSpeed -= minHeap.shift(); // Remove the engineer with the smallest speed
        }

        // Step 6: Compute performance with current team
        maxPerf = Math.max(maxPerf, totalSpeed * eff);
    }

    // Step 7: Return the maximum performance modulo 10^9 + 7
    return maxPerf % MOD;
};

Time Complexity Analysis: O(n log n + k log k)

Pair Creation and Sorting: O(n log n)

  • We create n pairs (efficiency[i], speed[i]) and sort them in descending order based on efficiency.
  • Sorting takes O(nlogn) time.

Min Heap Operations: O(k log k)

  • We maintain a min heap to track the top k speeds.
  • Each insertion takes O(log k) time.
  • Since we insert at most k elements, this step takes O(klogk) time.

Dynamic Updates for Remaining Elements: O((n-k) log k)

  • For the remaining n - k elements, we insert a new speed and remove the smallest speed from the heap.
  • Each heap update (removal + insertion) takes O(logk).
  • Since we perform this operation n - k times, the total cost is O((n−k)logk).

Performance Calculation: O(n)

  • We iterate through all n elements, computing the current performance.
  • This takes O(n) time.

Final Time Complexity: O(n log n) + O(k log k) + O((n-k) log k) = O(n log n + k log k)

  • Since k ≤ n, we simplify to O(n log n ), which is efficient for large inputs.

Space Complexity Analysis: O(n)

Auxiliary Space Complexity: O(n)

  • We store n pairs (efficiency[i], speed[i]) in a vector, requiring O(n) space.
  • A min heap maintains at most k elements, requiring O(k) space.
  • Other variables (totalSpeed, loop counters) require O(1) space.

Input Storage: O(n)

  • The input arrays speed and efficiency take O(n) space.
  • Sorting is done in place, so no extra space is needed.

Final Space Complexity:O(n) (input storage) + O(k) (heap) = O(n) (since k ≤ n).

Similar Problems

Now we have successfully tackled this problem, let’s try these similar problems.

Maximum Average Pass Ratio

Given a set of classes where each class has a certain number of passing students and total students, and extra students who are guaranteed to pass, the goal is to distribute these extra students in a way that maximizes the overall average pass ratio across all classes.

Maximum Subsequence Score

Given two integer arrays nums1 and nums2 of equal length n, and an integer k, select a subsequence of k indices from nums1.
The score of a chosen subsequence is defined as:
(sum of selected elements from nums1)×(minimum of selected elements from nums2)
Return the maximum possible score.