Skip to main content

Heaps

Maximum Subsequence Score Solution In C++/Python/Java/JS

Problem Description

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.
For chosen indices i0, i1, ..., ik - 1, your score is defined as:
The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).
Return the maximum possible score.
A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

Example

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation:
The four possible subsequence scores are:

  • We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
  • We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
  • We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
  • We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
    Therefore, we return the max score, which is 12.


Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation:
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 105
  • 0 <= nums1[i], nums2[j] <= 105
  • 1 <= k <= n
💡
Try it Yourself First
To maximize the score, sort pairs by efficiency and maintain a min heap for the top k values. Iteratively update the sum and compute the best score dynamically.

Brute Force Approach

Intuition

Our goal is to maximize the score by selecting exactly k elements from nums1 while ensuring that the minimum value from the corresponding elements in nums2 contributes to the final score. To achieve this, we must explore all possible combinations of k elements and determine the maximum possible product of their sum and the smallest associated value from nums2.

We first pair each element from nums2 with its corresponding element in nums1, treating nums2[i] as the constraint that determines the multiplier for a valid selection. The challenge is to find the subset of k elements that maximizes the sum of selected nums1 values while keeping the smallest nums2 value in the subset as large as possible.

To systematically explore all valid subsets, we use a recursive combination-generation approach. Starting from the first element, we either include it in the current subset or skip it, then proceed to the next index. When we reach exactly k elements in our subset, we compute the score by multiplying the sum of selected nums1 values by the minimum nums2 value within that subset. We then compare this score with the global maximum and update accordingly.

By iterating through all possible subsets, we ensure that we don't miss any optimal selection. However, as the number of elements grows, the recursive approach can become computationally expensive since we are generating and evaluating all combinations. This brute-force method guarantees an optimal result but may not be the most efficient for larger inputs.

Approach

Step 1: Pair and Sort the Elements

  • Create a vector of pairs where each element from nums2 is paired with the corresponding element from nums1.
  • Sorting is not required in this approach, but we maintain the order to ensure correct combination generation.

Step 2: Generate Combinations Recursively

  • Implement a recursive function generateCombinations to explore all subsets of size k.
  • The function takes the current index, the selected elements, the sum of selected nums1 values, and the global result variable.

Step 3: Base Case for Combination Selection

  • If k elements are selected, find the minimum nums2 value from the chosen indices.
  • Compute the score as the product of the sum of selected nums1 values and the minimum nums2 value.
  • Update the global maximum score if the new score is higher.

Step 4: Explore Possible Selections

  • Iterate over the remaining elements, adding the current element to the selection.
  • Recursively call generateCombinations with the next index, updating the sum of nums1.
  • Backtrack by removing the last added element to explore other possibilities.

Step 5: Compute and Return Maximum Score

  • After exploring all combinations, return the highest score found during the recursive process.

Dry Run

Input:

  • nums1 = [2, 1, 4, 5],nums2 = [3, 2, 1, 6]
  • k: 2

Step 1: Pair and Sort Elements

  • Pair nums2 elements with corresponding nums1 values:
  • pairs = [(3,2), (2,1), (1,4), (6,5)]

Step 2: Generate Combinations Recursively

  • We need to find all combinations of 2 elements from pairs and compute the maximum score.

Step 3: Exploring Combinations

Choose (3,2) and (2,1):

  • Sum of nums1 = 2 + 1 = 3
  • Minimum in nums2 = min(3,2) = 2
  • Score = 3 × 2 = 6

Choose (3,2) and (1,4):

  • Sum of nums1 = 2 + 4 = 6
  • Minimum in nums2 = min(3,1) = 1
  • Score = 6 × 1 = 6

Choose (3,2) and (6,5):

  • Sum of nums1 = 2 + 5 = 7
  • Minimum in nums2 = min(3,6) = 3
  • Score = 7 × 3 = 21 (maximum so far)

Choose (2,1) and (1,4):

  • Sum of nums1 = 1 + 4 = 5
  • Minimum in nums2 = min(2,1) = 1
  • Score = 5 × 1 = 5

Choose (2,1) and (6,5):

  • Sum of nums1 = 1 + 5 = 6
  • Minimum in nums2 = min(2,6) = 2
  • Score = 6 × 2 = 12

Choose (1,4) and (6,5):

  • Sum of nums1 = 4 + 5 = 9
  • Minimum in nums2 = min(1,6) = 1
  • Score = 9 × 1 = 9

Step 4: Compute Final Maximum Score

  • The highest computed score is 21.

Final Output: 21

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

class Solution {  
public:  
    // Helper function to generate k-combinations and compute the max score  
    void generateCombinations(vector<pair<int, int>>& pairs, int start, int k,  
                              vector<int>& curr, long long& result, long long currSum) {  
        // Step 1: Base case - if k elements are selected  
        if (curr.size() == k) {  
            long long minVal = INT_MAX;  

            // Step 2: Find the minimum value in nums2 for selected indices  
            for (int idx : curr) {  
                minVal = min(minVal, (long long)pairs[idx].first);  
            }  

            // Step 3: Update the maximum score  
            result = max(result, currSum * minVal);  
            return;  
        }  

        // Step 4: Iterate through remaining elements and generate combinations  
        for (int i = start; i < pairs.size(); i++) {  
            curr.push_back(i);  
            generateCombinations(pairs, i + 1, k, curr, result, currSum + pairs[i].second);  
            curr.pop_back();  
        }  
    }  

    // Function to compute the maximum score using sorting and recursive combinations  
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {  
        int n = nums1.size();  
        vector<pair<int, int>> pairs(n);  

        // Step 1: Store elements as (nums2[i], nums1[i]) pairs  
        for (int i = 0; i < n; i++) {  
            pairs[i] = {nums2[i], nums1[i]};  
        }  

        long long result = 0;  
        vector<int> curr;  

        // Step 2: Generate all k-combinations and find the maximum score  
        generateCombinations(pairs, 0, k, curr, result, 0);  

        // Step 3: Return the maximum possible score  
        return result;  
    }  
};

Java 
// Approach: Sorting with Recursive Combinations  
// Language: Java 

import java.util.*;

class Solution {
    // Helper function to generate k-combinations and compute the max score
    private void generateCombinations(List<int[]> pairs, int start, int k,
                                      List<Integer> curr, long[] result, long currSum) {
        // Base case: If k elements are selected
        if (curr.size() == k) {
            long minVal = Long.MAX_VALUE;

            // Find the minimum value in nums2 for selected indices
            for (int idx : curr) {
                minVal = Math.min(minVal, pairs.get(idx)[0]);
            }

            // Update the maximum score
            result[0] = Math.max(result[0], currSum * minVal);
            return;
        }

        // Iterate through remaining elements and generate combinations
        for (int i = start; i < pairs.size(); i++) {
            curr.add(i);
            generateCombinations(pairs, i + 1, k, curr, result, currSum + pairs.get(i)[1]);
            curr.remove(curr.size() - 1);
        }
    }

    // Function to compute the maximum score using sorting and recursive combinations
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        List<int[]> pairs = new ArrayList<>();

        // Store elements as (nums2[i], nums1[i]) pairs
        for (int i = 0; i < n; i++) {
            pairs.add(new int[]{nums2[i], nums1[i]});
        }

        long[] result = new long[1]; // Store max result
        List<Integer> curr = new ArrayList<>();

        // Generate all k-combinations and find the maximum score
        generateCombinations(pairs, 0, k, curr, result, 0);

        // Return the maximum possible score
        return result[0];
    }
}

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

from itertools import combinations

class Solution(object):
    # Function to compute the maximum score using sorting and recursive combinations
    def maxScore(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: int
        """
        # Step 1: Create pairs (nums2[i], nums1[i]) and sort by nums2 in descending order
        pairs = sorted(zip(nums2, nums1), reverse=True)
        max_score = 0

        # Step 2: Generate all k-combinations and find the maximum score
        for combination in combinations(pairs, k):
            sum_nums1 = sum(num1 for _, num1 in combination)  # Sum of selected nums1 values
            min_nums2 = min(num2 for num2, _ in combination)  # Minimum nums2 value in selected pairs
            max_score = max(max_score, sum_nums1 * min_nums2)  # Compute max score

        # Step 3: Return the maximum possible score
        return max_score

Javascript 
/**
 * Approach: Sorting with Recursive Combinations
 * Language: JavaScript
 *
 * @param {number[]} nums1 - First array of integers.
 * @param {number[]} nums2 - Second array of integers.
 * @param {number} k - Number of elements to select.
 * @return {number} - Maximum possible score.
 */
var maxScore = function(nums1, nums2, k) {
    let pairs = [];
    
    // Step 1: Store elements as (nums2[i], nums1[i]) pairs
    for (let i = 0; i < nums1.length; i++) {
        pairs.push([nums2[i], nums1[i]]);
    }
    
    // Step 2: Sort pairs by nums2 in descending order
    pairs.sort((a, b) => b[0] - a[0]);

    let maxScore = 0;

    // Step 3: Generate all k-combinations and find the maximum score
    const generateCombinations = (start, selected, currSum) => {
        if (selected.length === k) {
            let minVal = Math.min(...selected.map(idx => pairs[idx][0]));
            maxScore = Math.max(maxScore, currSum * minVal);
            return;
        }

        for (let i = start; i < pairs.length; i++) {
            selected.push(i);
            generateCombinations(i + 1, selected, currSum + pairs[i][1]);
            selected.pop();
        }
    };

    generateCombinations(0, [], 0);

    // Step 4: Return the maximum possible score
    return maxScore;
};

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

Sorting the Pairs (O(n log n))

  • We sort the pairs based on nums2 values 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 k elements 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 nums1 and find the minimum of nums2, 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 (nums2[i], nums1[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 curr of size O(k) to track combinations. The pairs 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

  • The recursive approach generates all possible ways to select k elements from n, which leads to O(n choose k) = O(n! / (k!(n-k)!)) combinations. In the worst case, this can approach O(n^k), making it infeasible for large inputs.

Why Does This Cause TLE?

  • When n = 100,000 and k is even moderately large (e.g., 20 or 30), the number of combinations grows exponentially, leading to billions or even trillions of operations. This far exceeds the typical time limit of 10⁸ operations per second, making brute force impractical.
The brute-force approach used recursive combinations, leading to exponential time complexity. To optimize, we switch to a Greedy + Min Heap strategy. Sorting the pairs by efficiency allows us to prioritize important elements first. The min heap dynamically tracks the top k values, ensuring we always maintain the best selection. Instead of recomputing sums for every combination, we efficiently update kSum in a single pass, leading to a much faster solution.

Optimal Approach

Intuition

The initial approach used recursive combinations to generate all possible selections, leading to an exponential time complexity. This was inefficient. To optimize, we use a greedy strategy combined with a priority queue (min heap) to maintain the top k values dynamically.

By sorting the pairs based on efficiency (nums2[i]), we ensure that we always consider the most efficient elements first. We maintain a running sum of the top k values and use a min heap to track the smallest value in the selection. This allows us to efficiently adjust our selection when adding new elements.

Instead of recomputing the sum for every combination, we iteratively update the kSum by adding the new element and removing the smallest when k+1 elements exist. This ensures that we always have the best k elements, maximizing the overall score. By multiplying kSum with the current efficiency value, we compute the best possible score dynamically in a single pass.

Approach

Step 1: Create Pairs and Sort by Efficiency

  • Construct an array of pairs (nums2[i], nums1[i]), where nums2[i] represents efficiency, and nums1[i] represents the value.
  • Sort this array in descending order based on efficiency (nums2[i]). This ensures that we prioritize higher efficiency values first.

Step 2: Initialize Min Heap and Variables

  • Use a min heap (minHeap) to maintain the top k values dynamically.
  • Initialize kSum = 0 to store the sum of selected values.
  • Initialize ans = 0 to store the maximum possible score.

Step 3: Iterate Over Sorted Pairs

  • For each pair (efficiency, value):
    • Push value into the min heap and add it to kSum.
    • If the heap size exceeds k, remove the smallest value and update kSum.
    • If the heap size is exactly k, compute the current score as kSum * efficiency.
    • Update ans with the maximum score encountered so far.

Step 4: Return the Result

  • The final answer ans holds the maximum possible score based on the optimal selection of k values.
  • Return ans.

Dry Run

Input:

  • nums1 = [2, 1, 4, 5]
  • nums2 = [3, 2, 1, 6]
  • k: 2

Step 1: Pair and Sort Elements

  • Pair elements from nums2 with corresponding nums1: pairs = [(3,2), (2,1), (1,4), (6,5)]
  • Sort pairs by efficiency (nums2[i]) in descending order: sorted_pairs = [(6,5), (3,2), (2,1), (1,4)]

Step 2: Initialize Min Heap and Variables

  • minHeap = [] (to track the top k values)
  • kSum = 0 , ans = 0

Step 3: Iterate Over Sorted Pairs

Iteration 1: Process (6,5)

  • Add 5 to minHeap: [5]
  • Update kSum: 5
  • Heap size < k, so no score calculation yet.

Iteration 2: Process (3,2)

  • Add 2 to minHeap: [2, 5]
  • Update kSum: 5 + 2 = 7
  • Heap size is now k, compute score :
    • Score = 7 × 3 = 21
  • Update ans = 21.

Iteration 3: Process (2,1)

  • Add 1 to minHeap: [1, 2, 5]
  • Update kSum: 7 + 1 = 8
  • Heap size exceeds k, remove smallest (1):
    • minHeap = [2, 5]
    • kSum = 8 - 1 = 7
  • Compute score:
    • Score = 7 × 2 = 14 (No update, 21 is max).

Iteration 4: Process (1,4)

  • Add 4 to minHeap: [2, 4, 5]
  • Update kSum: 7 + 4 = 11
  • Heap size exceeds k, remove smallest (2):
    • minHeap = [4, 5]
    • kSum = 11 - 2 = 9
  • Compute score:
    • Score = 9 × 1 = 9 (No update, 21 is max).

Step 4: Compute Final Maximum Score

  • The highest score encountered is 21.

Final Output: 21

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    // Function to compute the maximum score using a greedy approach
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        vector<pair<int, int>> vec(n);

        // Step 1: Create pairs of (nums2[i], nums1[i]) for sorting
        for (int i = 0; i < n; ++i) {
            vec[i] = {nums2[i], nums1[i]};
        }

        // Step 2: Sort pairs in descending order based on nums2 values
        sort(vec.begin(), vec.end(), greater<pair<int, int>>());

        // Step 3: Initialize a min heap to track the smallest k values from nums1
        priority_queue<int, vector<int>, greater<int>> minh;
        long long kSum = 0;

        // Step 4: Compute sum of first k elements and push them into the min heap
        for (int i = 0; i < k; ++i) {
            kSum += vec[i].second;
            minh.push(vec[i].second);
        }

        // Step 5: Calculate initial answer using k-th efficiency value
        long long ans = kSum * vec[k - 1].first;

        // Step 6: Iterate through remaining elements and update max score dynamically
        for (int i = k; i < n; ++i) {
            kSum += vec[i].second - minh.top();
            minh.pop();
            minh.push(vec[i].second);
            ans = max(ans, kSum * vec[i].first);
        }

        // Step 7: Return the final maximum score
        return ans;
    }
};

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

import java.util.*;

class Solution {

    // Function to compute the maximum score using a greedy approach
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        
        // Step 1: Create a list of pairs (nums2[i], nums1[i]) for sorting
        List<int[]> pairs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            pairs.add(new int[]{nums2[i], nums1[i]});
        }

        // Step 2: Sort pairs in descending order based on nums2 values
        pairs.sort((a, b) -> Integer.compare(b[0], a[0]));

        // Step 3: Initialize a min heap to track the smallest k values from nums1
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        long kSum = 0;

        // Step 4: Compute sum of first k elements and push them into the min heap
        for (int i = 0; i < k; i++) {
            kSum += pairs.get(i)[1];
            minHeap.offer(pairs.get(i)[1]);
        }

        // Step 5: Calculate initial answer using k-th efficiency value
        long maxScore = kSum * pairs.get(k - 1)[0];

        // Step 6: Iterate through remaining elements and update max score dynamically
        for (int i = k; i < n; i++) {
            kSum += pairs.get(i)[1] - minHeap.poll(); // Remove smallest and add new element
            minHeap.offer(pairs.get(i)[1]); // Maintain k elements in minHeap
            maxScore = Math.max(maxScore, kSum * pairs.get(i)[0]); // Update max score
        }

        // Step 7: Return the final maximum score
        return maxScore;
    }
}

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

import heapq

class Solution:
    # Function to compute the maximum score using a greedy approach
    def maxScore(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums1)
        
        # Step 1: Create a list of tuples (nums2[i], nums1[i]) for sorting
        pairs = [(nums2[i], nums1[i]) for i in range(n)]

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

        # Step 3: Initialize a min heap to track the smallest k values from nums1
        min_heap = []
        k_sum = 0

        # Step 4: Compute sum of first k elements and push them into the min heap
        for i in range(k):
            k_sum += pairs[i][1]
            heapq.heappush(min_heap, pairs[i][1])

        # Step 5: Calculate initial answer using k-th efficiency value
        max_score = k_sum * pairs[k - 1][0]

        # Step 6: Iterate through remaining elements and update max score dynamically
        for i in range(k, n):
            k_sum += pairs[i][1] - heapq.heappop(min_heap)  # Remove smallest and add new element
            heapq.heappush(min_heap, pairs[i][1])  # Maintain k elements in minHeap
            max_score = max(max_score, k_sum * pairs[i][0])  # Update max score

        # Step 7: Return the final maximum score
        return max_score

Javascript 
/** 
 * Approach: Greedy Algorithm with Min Heap (Priority Queue)
 * Language: JavaScript
 *
 * @param {number[]} nums1 - First array representing values.
 * @param {number[]} nums2 - Second array representing efficiency factors.
 * @param {number} k - Number of elements to select.
 * @return {number} - Maximum possible score.
 */
var maxScore = function(nums1, nums2, k) {
    // Step 1: Create pairs of [nums2[i], nums1[i]] and sort in descending order by nums2[i]
    let pairs = nums1.map((val, i) => [nums2[i], val]);
    pairs.sort((a, b) => b[0] - a[0]);

    // Step 2: Min heap to track the smallest k elements from nums1
    let minHeap = new MinPriorityQueue({ priority: (val) => val });
    let kSum = 0, maxScore = 0;

    // Step 3: Compute initial k elements sum and push into heap
    for (let i = 0; i < k; i++) {
        kSum += pairs[i][1];
        minHeap.enqueue(pairs[i][1]);
    }

    // Step 4: Calculate initial max score
    maxScore = kSum * pairs[k - 1][0];

    // Step 5: Iterate through remaining elements and update max score dynamically
    for (let i = k; i < nums1.length; i++) {
        kSum += pairs[i][1] - minHeap.dequeue().element; // Remove smallest and add new element
        minHeap.enqueue(pairs[i][1]); // Maintain k elements in heap
        maxScore = Math.max(maxScore, kSum * pairs[i][0]); // Update max score
    }

    // Step 6: Return the final maximum score
    return maxScore;
};

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

Heap Construction: O(n log n)

  • We create n pairs and sort them in descending order based on nums2[i].
  • Sorting takes O(n log n) time.

Min Heap Operations: O(k log k)

  • We insert k elements from nums1 into a min heap.
  • Each insertion takes O(log k) time.
  • Since we insert k elements, this takes O(k log k) time.
  • If heapify is used, it improves to O(k).

Dynamic Updates: O((n-k) log k)

  • For each of the remaining n-k elements :
  • We remove the smallest element (O(log k)).
  • We insert a new element (O(log k)).
  • This process runs n-k times.
  • Total time: O((n-k) log k).

Final Pass Ratio Calculation: O(n)

  • We iterate through all n classes to compute the final average pass ratio.
  • 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 + k log k), which is efficient for large inputs.

Space Complexity Analysis: O(n)

Auxiliary Space Complexity: O(n)

  • We store n pairs (nums2[i], nums1[i]) in a vector, requiring O(n) space.
  • A min heap stores at most k elements, requiring O(k) space.
  • Other variables (e.g., kSum, loop counters) require O(1) space.

Total Space Complexity: O(n)

  • The input arrays nums1 and nums2 take O(n) space.
  • Additional storage (vector + heap) takes O(n) in the worst case.

Final Space Complexity: O(n) (input storage) + O(n) (auxiliary storage) = O(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.

Minimum Operations to Reduce an Integer to 0

Given an array nums and an integer p, we need to form p pairs such that the maximum absolute difference among all pairs is minimized. Each index can be used only once. Sorting the array helps, and we can use binary search with a greedy approach to efficiently find the optimal minimum maximum difference.