Maximum Subsequence Score — InterviewPrepKit

Solving tips

Key insight: the score mixes an additive sum with a min bottleneck, so fix the bottleneck by sorting pairs by nums2 descending.
Sweep in that order treating the current nums2 as the minimum multiplier; keep the k largest nums1 among elements seen in a size-k min-heap with a running sum.
Only record running_sum × current_nums2 when the heap holds exactly k items, and always subtract popped values from the sum.
Target O(n log n) time and O(n) space; seed best = 0 since values can be 0, and sort by nums2 (not nums1).

Problem

You are given two integer arrays nums1 and nums2, both of length n, and a positive integer k.

You must choose a subsequence of exactly k indices i_1, i_2, ..., i_k (the indices, not the values, must be distinct). For a chosen set of indices, the score is defined as:

(sum of the selected nums1 values) × (minimum of the selected nums2 values)

That is, add up the nums1 entries at your chosen indices, then multiply that sum by the smallest nums2 entry among those same indices.

Return the maximum possible score over all valid choices of k indices.

Examples

Input: nums1 = [1, 3, 3, 2], nums2 = [2, 1, 3, 4], k = 3 → Output: 12 Pick indices {0, 2, 3}. nums1 sum = 1 + 3 + 2 = 6; nums2 min = min(2, 3, 4) = 2; score = 6 × 2 = 12. No other triple beats it.
Input: nums1 = [4, 2, 3, 1, 1], nums2 = [7, 5, 10, 9, 6], k = 1 → Output: 30 With k = 1, score is just nums1[i] × nums2[i]. Index 2 gives 3 × 10 = 30, the best single pick.
Input: nums1 = [2, 1, 14, 12], nums2 = [11, 7, 5, 5], k = 2 → Output: 130 Pick indices {0, 3}: sum 2 + 12 = 14, min min(11, 5) = 5, score 70. Pick {0, 1}: sum 3, min 7, score 21. Best is {2, 3}? sum 26, min 5 = 130. Answer 130.

Constraints

n == nums1.length == nums2.length, with 1 <= n <= 10^5.
0 <= nums1[i], nums2[j] <= 10^5.
1 <= k <= n.

The 10^5 size rules out anything close to trying all C(n, k) subsets — you need roughly O(n log n).

Think about it first

Hint 1

The score couples two things that pull against each other: you want a large nums1 sum, but the multiplier is the *minimum* nums2 in the chosen set. What if you fixed which element is that minimum?

Hint 2

Sort the index pairs by their `nums2` value in **descending** order. If you scan in that order and treat the current element as the minimum multiplier, then everything you've already seen has a `nums2` value at least as large — so any of them is a legal partner.

Hint 3

For a fixed minimum, you want the `k` largest `nums1` values among the eligible elements. Maintain a **min-heap** of size `k` over the nums1 values plus a running sum; each new element becomes a candidate minimum, and `running_sum × current_nums2` is a candidate answer.

TL;DR

Sort pairs by nums2 descending, sweep while keeping the k largest nums1 values in a min-heap with a running sum — O(n log n) time, O(n) space.

Approach 1 — Brute force: try every k-subset

The naive intuition enumerates all combinations of k indices, computes each score, and keeps the maximum.

from itertools import combinations
from typing import List

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)
        best = 0
        for combo in combinations(range(n), k):
            total = sum(nums1[i] for i in combo)
            minimum = min(nums2[i] for i in combo)
            best = max(best, total * minimum)
        return best

Complexity: O(C(n, k) · k) time. There are up to C(10^5, k) subsets — astronomically many — so the constraints obliterate this. It exists only to state the definition precisely.

Approach 2 — Sort by nums2 desc + min-heap of the top-k nums1

The insight: the multiplier is the minimum nums2 in the chosen set, so pin it down. Sort all (nums2[i], nums1[i]) pairs by nums2 descending. Now sweep left to right; when you reach a pair, its nums2 is the smallest among everything seen so far, so treat it as the minimum multiplier. Among all elements seen so far you’re free to pick any k of them (all have a nums2 at least this large), and to maximize the score you want the k largest nums1 values. A min-heap of size k plus a running sum tracks exactly that: push each nums1, and when the heap grows past k, pop the smallest and subtract it from the sum. Whenever the heap holds exactly k items, running_sum × current_nums2 is a valid candidate.

import heapq
from typing import List

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

        min_heap: List[int] = []
        running_sum = 0
        best = 0

        for n2, n1 in pairs:
            heapq.heappush(min_heap, n1)
            running_sum += n1
            if len(min_heap) > k:
                running_sum -= heapq.heappop(min_heap)
            if len(min_heap) == k:
                best = max(best, running_sum * n2)

        return best

Walkthrough on nums1 = [1, 3, 3, 2], nums2 = [2, 1, 3, 4], k = 3:

Pairs sorted by nums2 desc: (4, 2), (3, 3), (2, 1), (1, 3).
(4, 2): heap [2], sum 2, size 1 < 3.
(3, 3): heap [2, 3], sum 5, size 2 < 3.
(2, 1): heap [1, 3, 2], sum 6, size 3 → candidate 6 × 2 = 12. best = 12.
(1, 3): push 3 → sum 9, size 4 > 3, pop smallest 1 → sum 8, heap [2, 3, 3], size 3 → candidate 8 × 1 = 8. best stays 12.

Answer: 12, matching the example (indices {0, 2, 3}).

Complexity: O(n log n) time (the sort dominates; each of the n heap operations is O(log k)), O(n) space for the sorted pairs and the heap.

Common pitfalls

Sorting by nums1 instead of nums2. The multiplier is the min of nums2; that is what must be pinned by the sort order.
Only evaluating when the heap is exactly size k. Before you have k elements the subsequence is incomplete; computing a score early gives wrong answers.
Forgetting to subtract the popped value from the running sum. The sum must always equal the total of the values currently in the heap.
Initializing best too high. Values can be 0 (e.g. a nums1 entry of 0), so best = 0 is a safe floor; never seed it with a made-up large negative that could survive if all scores are 0.

Pattern takeaway

When a score mixes an additive term with a bottleneck (min/max) term, fix the bottleneck by sorting on it, then let a size-k heap greedily maintain the best additive part among everything still eligible. “Sort to fix the minimum, heap to keep the top-k” recurs across many two-array optimization problems.