LeetCode Problem 2542

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

LeetCode 2542 - Maximum Subsequence Score

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, both of the same length n, along with an integer k. We must choose exactly k indices from the arrays. The chosen indices form a subsequence, meaning the selected positions come from the original arrays without modifying the arrays themselves.

For the selected indices, the score is computed using two parts:

1. The sum of the corresponding values from nums1
2. The minimum of the corresponding values from nums2

The final score is:

$$(\text{sum of selected nums1 values}) \times (\text{minimum selected nums2 value})$$

Our goal is to maximize this score.

A key detail is that the minimum value from nums2 acts as a multiplier for the entire sum. This creates an interesting tradeoff:

• We want large values from nums1 to maximize the sum.
• We also want a large minimum value from nums2, because it multiplies the whole sum.

The constraints are important:

• n can be as large as 100000
• A brute-force solution that checks all subsequences is impossible
• We need something close to O(n log n) to handle the input size efficiently

The problem guarantees:

• Both arrays have the same length
• k is always valid, meaning 1 <= k <= n
• Values are non-negative integers

Several edge cases are important to keep in mind:

• k = 1, where the answer becomes the maximum product nums1[i] * nums2[i]
• k = n, where every element must be selected
• Arrays containing zeros, which can reduce the score to zero
• Large values that may overflow 32-bit integers, especially in Go

Approaches

Brute Force Approach

The most direct approach is to generate every possible subsequence of size k. For each subsequence:

1. Compute the sum of selected nums1 values
2. Compute the minimum selected nums2 value
3. Multiply them to get the score
4. Track the maximum score

This approach is correct because it evaluates every valid choice.

However, it is far too slow. The number of subsequences is:

$$\binom{n}{k}$$

In the worst case, this becomes astronomically large. Even for moderate values of n, enumerating all combinations is infeasible.

Key Insight for the Optimal Solution

The critical observation is that when a set of indices is chosen, the minimum value from nums2 determines the multiplier.

Suppose we decide that a particular element from nums2 will be the minimum value in the chosen subsequence. Then:

• Every selected nums2 value must be at least that large
• Among all valid candidates, we want the largest possible sum from nums1

This suggests sorting the pairs (nums1[i], nums2[i]) in descending order of nums2.

As we iterate through the sorted pairs:

• The current nums2 value becomes the smallest possible multiplier for the current group
• We need to choose the best k values from nums1 among all elements seen so far

To efficiently maintain the largest k values from nums1, we use a min-heap.

The heap allows us to:

• Keep only the best k candidates
• Quickly remove the smallest nums1 value when necessary
• Maintain the current sum efficiently

This transforms the problem into an efficient greedy + heap solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C(n, k) * k)	O(k)	Tries every possible subsequence
Optimal	O(n log k)	O(k)	Sort + greedy + min-heap

Algorithm Walkthrough

Step 1: Pair the Arrays Together

Create pairs of values:

(nums1[i], nums2[i])

This keeps the relationship between corresponding elements intact.

Step 2: Sort by nums2 in Descending Order

Sort all pairs by nums2 from largest to smallest.

Why?

Because when processing a pair with value nums2 = x, every previously seen element has nums2 >= x.

That means if we choose a subsequence ending at this position, the minimum nums2 value will be exactly x.

Step 3: Use a Min-Heap for nums1

We now iterate through the sorted pairs.

For each pair:

1. Add the nums1 value into a min-heap
2. Add it to a running sum

The heap stores the currently selected nums1 values.

Step 4: Keep Only the Largest k Values

If the heap size exceeds k:

• Remove the smallest element
• Subtract it from the running sum

This guarantees that the heap always contains the largest possible k values among the processed elements.

Step 5: Compute Candidate Scores

Whenever the heap size becomes exactly k:

• The current nums2 value is the minimum multiplier
• The running sum is the best possible sum for this multiplier

Compute:

$$\text{score} = \text{currentSum} \times \text{currentNums2}$$

Update the answer if this score is larger.

Step 6: Return the Maximum Score

After processing all pairs, the maximum recorded score is the answer.

Why it works

The algorithm works because of the sorting order. At each iteration, the current nums2 value is guaranteed to be the minimum among all processed elements. Therefore, any valid subsequence using the current element has a fixed multiplier.

Given that fixed multiplier, the best strategy is to maximize the sum of selected nums1 values. The min-heap ensures we always keep the largest possible k values from nums1.

Thus, every possible minimum multiplier is considered exactly once, and for each multiplier we compute the optimal sum. This guarantees the global optimum.

Python Solution

from typing import List
import heapq

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = sorted(
            zip(nums2, nums1),
            reverse=True
        )

        min_heap = []
        current_sum = 0
        best_score = 0

        for num2_value, num1_value in pairs:
            heapq.heappush(min_heap, num1_value)
            current_sum += num1_value

            if len(min_heap) > k:
                removed = heapq.heappop(min_heap)
                current_sum -= removed

            if len(min_heap) == k:
                score = current_sum * num2_value
                best_score = max(best_score, score)

        return best_score

The implementation begins by combining the arrays into pairs. Notice that the sorting order uses nums2 first, because the algorithm revolves around fixing the minimum multiplier.

The min-heap stores the currently chosen nums1 values. Python's heapq module provides an efficient min-heap implementation.

The variable current_sum tracks the sum of elements currently inside the heap. This avoids recomputing the sum repeatedly.

Whenever the heap grows larger than k, we remove the smallest nums1 value. This ensures we keep the largest possible contribution to the sum.

When the heap size becomes exactly k, we compute a candidate score using the current nums2 value as the minimum multiplier.

Finally, the largest score found during iteration is returned.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

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 maxScore(nums1 []int, nums2 []int, k int) int64 {
	n := len(nums1)

	pairs := make([][2]int, n)

	for i := 0; i < n; i++ {
		pairs[i] = [2]int{nums2[i], nums1[i]}
	}

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

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

	var currentSum int64
	var bestScore int64

	for _, pair := range pairs {
		num2Value := pair[0]
		num1Value := pair[1]

		heap.Push(minHeap, num1Value)
		currentSum += int64(num1Value)

		if minHeap.Len() > k {
			removed := heap.Pop(minHeap).(int)
			currentSum -= int64(removed)
		}

		if minHeap.Len() == k {
			score := currentSum * int64(num2Value)

			if score > bestScore {
				bestScore = score
			}
		}
	}

	return bestScore
}

The Go implementation follows the same algorithmic structure as the Python solution. The main difference is that Go requires a custom heap implementation using the container/heap package.

Another important difference is integer overflow handling. Since scores can become very large, the implementation uses int64 for sums and final scores.

The heap stores regular integers, but all arithmetic related to scores is converted to int64.

Worked Examples

Example 1

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

First create pairs and sort descending by nums2:

nums2	nums1
4	2
3	3
2	1
1	3

Now process step by step.

Step	Current Pair	Heap	Current Sum	Multiplier	Score	Best
1	(4,2)	[2]	2	-	-	0
2	(3,3)	[2,3]	5	-	-	0
3	(2,1)	[1,3,2]	6	2	12	12
4	(1,3)	[1,2,3,3]	9	-	-	12

Heap exceeds size k, remove smallest:

Step	Heap After Removal	Current Sum
4	[2,3,3]	8

Now compute:

$$8 \times 1 = 8$$

Best score remains 12.

Final answer:

12

Example 2

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

Sorted pairs:

nums2	nums1
10	3
9	1
7	4
6	1
5	2

Process step by step.

Step	Current Pair	Heap	Current Sum	Score	Best
1	(10,3)	[3]	3	30	30
2	(9,1)	[1,3]	4	-	30

Remove smallest:

Heap	Sum
[3]	3

Compute:

$$3 \times 9 = 27$$

Continue similarly.

The maximum score remains:

30

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, heap operations are O(log k)
Space	O(n)	Sorting storage plus heap

The sorting step requires O(n log n) time. During iteration, each element is inserted into the heap once and possibly removed once. Heap operations cost O(log k) each, giving O(n log k) total heap work.

Since k <= n, the sorting step dominates overall complexity.

The heap stores at most k elements, while the sorted pairs require O(n) storage.

Test Cases

from typing import List
import heapq

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = sorted(zip(nums2, nums1), reverse=True)

        min_heap = []
        current_sum = 0
        best_score = 0

        for num2_value, num1_value in pairs:
            heapq.heappush(min_heap, num1_value)
            current_sum += num1_value

            if len(min_heap) > k:
                current_sum -= heapq.heappop(min_heap)

            if len(min_heap) == k:
                best_score = max(best_score, current_sum * num2_value)

        return best_score

solution = Solution()

assert solution.maxScore([1,3,3,2], [2,1,3,4], 3) == 12
# provided example 1

assert solution.maxScore([4,2,3,1,1], [7,5,10,9,6], 1) == 30
# provided example 2

assert solution.maxScore([5], [7], 1) == 35
# single element arrays

assert solution.maxScore([1,2,3], [4,5,6], 3) == 24
# k equals n

assert solution.maxScore([0,0,0], [1,2,3], 2) == 0
# all nums1 values are zero

assert solution.maxScore([5,1,5], [0,10,2], 2) == 12
# includes zero in nums2

assert solution.maxScore([10,9,8], [1,1,1], 2) == 19
# identical nums2 values

assert solution.maxScore([100000,100000], [100000,100000], 2) == 20000000000
# large values stress overflow handling

assert solution.maxScore([2,1,14,12], [11,7,13,6], 3) == 168
# mixed values requiring heap replacement

Test	Why
Example 1	Validates the main sample case
Example 2	Validates k = 1 behavior
Single element arrays	Smallest valid input
k = n	Forces selection of all elements
All zeros in nums1	Score should become zero
Zero in nums2	Tests multiplier edge case
Identical nums2 values	Minimum stays constant
Large values	Verifies overflow safety
Heap replacement scenario	Confirms greedy logic correctness

Edge Cases

One important edge case occurs when k = 1. In this situation, every subsequence contains exactly one element, so the score becomes simply:

$$nums1[i] \times nums2[i]$$

A buggy implementation might still attempt unnecessary heap management logic or incorrectly assume multiple elements exist. The current implementation handles this naturally because the heap reaches size 1 immediately and computes scores correctly.

Another important case is when k = n. Here, every element must be selected. The minimum nums2 value becomes the global minimum of the entire array, and the sum becomes the total of all nums1 values. Some greedy algorithms fail because they attempt to discard elements unnecessarily. This implementation works correctly because the heap eventually contains all elements and never removes anything.

Arrays containing zeros are also significant. If the minimum selected nums2 value is zero, the entire score becomes zero regardless of the sum. Similarly, if all selected nums1 values sum to zero, the score is also zero. The algorithm handles this without any special logic because multiplication naturally produces the correct result.

Large integer values are another subtle source of bugs, especially in Go. The score can exceed the range of a 32-bit integer:

$$100000 \times (100000 \times 100000)$$

This is much larger than 2^31 - 1. The Go solution therefore uses int64 for all score-related calculations to prevent overflow.