LeetCode 2542 Maximum Subsequence Score in JS & C#

LeetCode 2542: Maximum Subsequence Score asks us to choose exactly k indices so that the sum of selected values from nums1 multiplied by the minimum selected value from nums2 is as large as possible. The key idea is to sort the pairs by nums2 and use a min-heap to keep the best possible k values from nums1.

This approach avoids checking every combination and gives an O(n log n) solution.

Problem Statement

You are given two arrays, nums1 and nums2, having the same length, along with an integer k. We need to select exactly k indices.

For the selected indices, the score is:

Score = sum(selected nums1 values) × minimum(selected nums2 values)

The goal is to find the maximum possible score.

Original problem: LeetCode 2542 - Maximum Subsequence Score

Problem: 2542. Maximum Subsequence Score
Difficulty: Medium
Topics: Sorting, Heap, Greedy

Examples

Example 1

nums1 = [1,3,3,2]
nums2 = [2,1,3,4]
k = 3

Output: 12

Choosing indices 0, 2, 3 gives:

(1 + 3 + 2) × min(2, 3, 4) = 6 × 2 = 12

Example 2

nums1 = [4,2,3,1,1]
nums2 = [7,5,10,9,6]
k = 1

Output: 30

Since k = 1, we choose one index. Index 2 gives 3 × 10 = 30, which is the maximum.

Constraints

• nums1 and nums2 have the same length.
• 1 ≤ n ≤ 100,000.
• Each value in both arrays is between 0 and 100,000.
• 1 ≤ k ≤ n.

With up to 100,000 elements, trying every combination of k indices is far too expensive. We need an approach close to O(n log n).

Intuition

The difficult part is that the score has two components:

1. We want a large sum from nums1.

2. We want a large minimum value from nums2.

The second part gives us the key to the problem.

Suppose we sort the paired values by nums2 in descending order:

(nums2, nums1)

Once we reach a particular pair, its nums2 value can be treated as the minimum nums2 value for the selected group.

So the problem becomes:

For every possible minimum nums2, keep the largest possible sum of k nums1 values among the elements seen so far.

This is exactly where the min-heap helps.

Why Do We Need a Min-Heap?

Imagine we have already processed several elements and need to keep exactly k values from nums1.

We want those k values to have the largest possible sum. Therefore, whenever we get a new nums1 value, we can add it to the heap.

If the heap now contains more than k values, we remove the smallest value.

                 Min-Heap

                  2
                /   \
               5     7
              / \
             8   9

        Smallest value = 2
              ↑
        Remove this one

This guarantees that the heap always contains the best k nums1 values from everything processed so far.

The Main Idea Visually

First, pair the arrays so that we never lose the relationship between nums1[i] and nums2[i].

nums1 = [1, 3, 3, 2]
nums2 = [2, 1, 3, 4]

Pairs:

nums2   nums1
  2       1
  1       3
  3       3
  4       2

Sort by nums2 descending:

nums2   nums1
  4       2
  3       3
  2       1
  1       3

Now, when we are at nums2 = 2, all elements seen so far have nums2 >= 2.

Therefore, if we choose any k elements from those processed elements, the minimum nums2 is guaranteed to be at least 2. At this point, we can calculate a candidate score.

Approach

Brute Force Idea

One straightforward idea would be to generate every possible group of k indices, calculate its nums1 sum and minimum nums2, and keep the maximum score.

However, the number of combinations can be enormous. With n as large as 100,000, this approach is not practical.

Optimal Approach

Step 1: Pair the values.

Create pairs containing nums2[i] and nums1[i]. This keeps both values belonging to the same index together.

Step 2: Sort by nums2 in descending order.

This allows the current nums2 value to represent the minimum possible nums2 for the elements processed so far.

Step 3: Maintain a min-heap of nums1 values.

Add each nums1 value to the heap and maintain at most k values. If there are more than k, remove the smallest one.

Step 4: Track the sum.

Instead of recalculating the sum of the heap every time, maintain a running sum. When a value enters the heap, add it. When the smallest value is removed, subtract it.

Step 5: Calculate the score.

Whenever the heap contains exactly k values:

score = current nums2 × sum of k nums1 values

Update the maximum score with this candidate.

Dry Run

Consider:

nums1 = [1, 3, 3, 2]
nums2 = [2, 1, 3, 4]
k = 3

After pairing and sorting by nums2 descending:

(4, 2)
(3, 3)
(2, 1)
(1, 3)

Step	Current Pair	Heap Values	Sum	Score
1	(4, 2)	[2]	2	Not enough elements
2	(3, 3)	[2, 3]	5	Not enough elements
3	(2, 1)	[1, 3, 2]	6	2 × 6 = 12
4	(1, 3)	[2, 3, 3]	8	1 × 8 = 8

The best score found during the process is 12.

Why Does This Work?

The important observation is that after sorting by nums2 in descending order, every element before the current element has a nums2 value greater than or equal to the current value.

Therefore, when the current value is x, any k elements selected from the processed portion have a minimum nums2 of at least x.

Among those processed elements, the min-heap keeps the k largest nums1 values. That gives us the maximum possible nums1 sum for that particular minimum nums2.

So at every step we are evaluating the best possible score whose limiting nums2 value is the current value.

Solution Code - JavaScript

var maxScore = function (nums1, nums2, k) {
    const pairs = nums1.map((num, index) => [nums2[index], num]);

    pairs.sort((a, b) => b[0] - a[0]);

    // Min Heap
    const heap = [];

    const push = (value) => {
        heap.push(value);

        let i = heap.length - 1;

        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);

            if (heap[parent] <= heap[i]) break;

            [heap[parent], heap[i]] = [heap[i], heap[parent]];
            i = parent;
        }
    };

    const pop = () => {
        const min = heap[0];
        const last = heap.pop();

        if (heap.length > 0) {
            heap[0] = last;

            let i = 0;

            while (true) {
                let smallest = i;
                const left = 2 * i + 1;
                const right = 2 * i + 2;

                if (
                    left < heap.length &&
                    heap[left] < heap[smallest]
                ) {
                    smallest = left;
                }

                if (
                    right < heap.length &&
                    heap[right] < heap[smallest]
                ) {
                    smallest = right;
                }

                if (smallest === i) break;

                [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
                i = smallest;
            }
        }

        return min;
    };

    let sum = 0;
    let max = 0;

    for (const [num2, num1] of pairs) {
        if (heap.length >= k && heap[0] > num1) {
            continue;
        }

        sum += num1;
        push(num1);

        if (heap.length > k) {
            sum -= pop();
        }

        if (heap.length === k) {
            max = Math.max(max, num2 * sum);
        }
    }

    return max;
};

Solution Code - C#

public class Solution {
    public long MaxScore(int[] nums1, int[] nums2, int k) {
        var pairs = nums1.Select((num, index )=> (num2: nums2[index], num1: num))
        .OrderByDescending(x => x.num2)
        .ToList();

        var minHeap = new PriorityQueue<int, int>();
        long max = 0;
        long sum =0;

        foreach(var pair in pairs){
            if(minHeap.Count >= k && minHeap.Peek() > pair.num1)continue;
            sum += pair.num1;
            minHeap.Enqueue(pair.num1, pair.num1);

            if(minHeap.Count > k){
                var n = minHeap.Dequeue();
                sum -= n;
            }

            if(minHeap.Count == k){
                max = Math.Max(max, pair.num2 * sum);
            }


        }
        return max;

        
    }
}

Code Walkthrough

Both implementations follow the same algorithm. The main difference is the heap implementation.

Pairing and Sorting

Each nums1[i] must stay connected to nums2[i], so the two values are stored together. The pairs are then sorted by nums2 in descending order.

Maintaining the Best k Values

The heap contains the current candidates from nums1. Because it is a min-heap, the smallest selected value is always available at the top. If we have more than k values, that smallest value is removed.

This means the heap effectively maintains the largest k nums1 values seen so far.

The Optimization in the C# and JavaScript Solutions

The condition that checks the smallest value in the heap before inserting can skip an unnecessary replacement when the heap already contains k values and the new nums1 value is smaller than the current minimum.

Skipping is safe because the current element has an equal or smaller nums2 value than the elements already processed. Replacing a larger nums1 value with a smaller one cannot improve the resulting sum.

Complexity Analysis

Time: O(n log n) — Sorting takes O(n log n), and each heap operation takes O(log k), giving an overall O(n log n) complexity.

Space: O(n) — The pairs require O(n) space, while the heap uses at most O(k).

Edge Cases

• k = 1: Each element is evaluated individually, so the answer is the maximum nums1[i] × nums2[i].
• k = n: All elements must be selected, so there is only one possible group.
• Zero values: Either array can contain zero, which can make the score zero.
• Duplicate values: Multiple pairs can have the same nums1 or nums2 value; the heap handles them normally.
• Large sums: The score can reach around 1015, so C# uses long. JavaScript's Number can represent these integer values exactly because they remain below Number.MAX_SAFE_INTEGER.

Common Mistakes and Tips

• Do not sort nums1 and nums2 independently. Their indices must remain connected.
• Sorting by nums2 descending is what lets the current value act as the minimum nums2.
• Use a min-heap, not a max-heap, because we need to remove the smallest nums1 value when the heap exceeds k.
• Keep a running sum instead of calculating the heap sum from scratch after every insertion.

FAQ

Why do we sort nums2 in descending order?

After sorting, when we reach a particular nums2 value, every previously processed element has a nums2 value at least as large. Therefore, the current value can serve as the minimum for the selected group.

Why is a min-heap used for Maximum Subsequence Score?

We want to keep the largest k values from nums1. A min-heap makes the smallest of those values immediately available, so it can be removed whenever the heap grows beyond k.

Can this problem be solved without a heap?

A heap is the standard efficient way to maintain the best k values while scanning the sorted pairs. Without an equivalent data structure, repeatedly finding and removing the smallest value can increase the complexity.

Related Problems

• LeetCode 1383 — Maximum Performance of a Team
• LeetCode 857 — Minimum Cost to Hire K Workers
• LeetCode 502 — IPO
• LeetCode 630 — Course Schedule III

Conclusion

The key to the LeetCode 2542 Maximum Subsequence Score solution is to stop thinking about all possible groups of k elements. Instead, sort by nums2 so that each current value represents a possible minimum, and use a min-heap to maintain the best k nums1 values seen so far.

The pattern is useful beyond this problem: when a score combines a sum of selected values with a minimum or maximum value, sorting around that limiting value and maintaining the best candidates with a heap can often turn an otherwise expensive combination problem into an efficient O(n log n) solution.