Algorithms · interview field notes

Maximum Subsequence Score

You are given two arrays paired by index. Choose k indices to maximize (sum of the chosen nums1) × (min of the chosen nums2). The min depends on which indices you pick, so the two factors interact — a larger sum often forces a smaller min. This page works through why sorting once and sweeping with a heap solves it in O(n log n).

score =

nums1[i₀] + nums1[i₁] + … + nums1[i₍ₖ₋₁₎]sum of the k chosen nums1

min( nums2[i₀] , … , nums2[i₍ₖ₋₁₎] )smallest of the k chosen nums2

example

i = 0

i = 1

i = 2

i = 3

nums1

nums2

k = 3 → best selection is {0, 2, 3}score = 12

The min is set by the whole group — how do you optimize a sum and a min at the same time?

Why does sorting by nums2 turn an exponential search into a single linear sweep?

The answer to memorize

One sort, one heap

The whole solution is two moves. Say them cleanly and stop:

Say this

"Sort the index-pairs by nums2 descending. Sweep left to right, pushing each nums1 into a min-heap; if the heap passes size k, pop the smallest. Whenever it holds exactly k, the current element's nums2 is the group's minimum, so heap_sum × nums2 is a candidate answer. Keep the max — O(n log n)."

That's it. The rest of this page is why those two moves are correct: why a descending sort, why the current element is always a legitimate minimum, and why a size-k heap is exactly the right bookkeeping.

Starting point

The objective: sum × min

Before optimizing, look at how the score behaves. With four items and k = 3 there are only four selections — enumerate them and notice that the best one is neither the largest sum nor the largest single min. The two factors trade off.

Brute force · try every choice of kfig

nums1nums2

i=0

i=1

i=2

i=3

press play to enumerate all four

pick {0, 1, 2}7 × 1= ·

pick {0, 1, 3}6 × 1= ·

pick {0, 2, 3}6 × 2= ·

pick {1, 2, 3}8 × 1= ·

We must pick k = 3 of the four indices. The score is sum of nums1 times the min of nums2. With only four columns we can just try all C(4, 3) = 4 choices.

01 / 06

Note: dropping index 1 (its nums2 = 1) shrank the sum yet gave the best score, because it raised the min from 1 to 2. The score is governed by whichever chosen element has the smallest nums2. That element has a name.

The key observation

Every selection has a bottleneck

The minimum isn't chosen independently — it's pinned to one chosen element: the one with the smallest nums2. Call it the bottleneck. If we decide the bottleneck first, every other pick simply has to sit at or above it.

Every selection has a bottleneckfig

{0,1,2}

{0,1,3}

{0,2,3}

{1,2,3}

Look again at the four selections. The min of nums2 in each is decided by one chosen element — its bottleneck.

01 / 04

Why sort by nums2

Sort everyone by nums2, largest first. Now "pick a bottleneck and only allow elements at or above it" becomes "stand on an element and only use the ones to its left." The minimum is now just a position in the sorted order, not a circular dependency.

The reframe

Fix the minimum, then maximize the sum

Instead of searching over selections, search over the value of the minimum. There are only n possible minimums (one per element). For each, the best selection is clear: take the top-k nums1 among the elements whose nums2 is at least that minimum, and multiply by the minimum. Try every minimum and keep the largest result.

Fix the minimum, then take the top-k nums1fig

minimum = nums2 ≥

pick

4i=3

pick

3i=2

pick

2i=0

1i=1

3 eligible (nums2 ≥ 2)

top-3 nums16×2=12◆ best

Minimum 2: 3 columns qualify, so take the top-3 nums1 (sum 6). Score = 6 × 2 = 12 — the best balance: a high enough minimum with a large enough sum.

there are only n candidate minimums — one per element. try them all, keep the max.

Say this

"Every selection's score equals (top-k nums1 sum among elements with nums2 ≥ some minimum) × that minimum. There are only n minimums worth trying, so I try them all and keep the maximum. A high minimum leaves too few elements to sum; a low minimum shrinks the multiplier — the best score is in between."

The algorithm

One sweep covers every minimum

Trying each minimum and recomputing the top-k from scratch is wasteful. But scanning minimums from high to low is just walking the sorted-descending list — and "the top-k nums1 seen so far" is exactly what a size-k min-heap maintains incrementally. The whole scan is one pass.

One sweep · sort by nums2 ↓ + size-k min-heapfig

4i=3

3i=2

2i=0

1i=1

sorted by nums2, highest first ──────▶ sweep

min-heap of nums1 · keep 3 biggestsize 0/3

empty

sum of heap = 0

candidate at this floor

heap not full yet

best score so far

Scanning floors top-down is just walking the sorted-descending list. And "top-k nums1 among everyone seen so far" is exactly what a size-k min-heap maintains. One left-to-right sweep does every floor at once.

01 / 06

Why the heap pops the smallest: once you hold k+1 candidates, the one with the least nums1 can never belong to an optimal sum at any lower minimum either — so evicting it permanently is safe. That greedy step is what keeps the sweep correct.

Correctness

Why the current element is a valid minimum

One detail deserves a clean answer. When we read sum × nums2[i], is nums2[i] really the minimum of the chosen k? Because we sorted descending, every element in the heap has nums2 ≥ nums2[i]. So the real minimum of that group is at least nums2[i] — meaning our candidate is never an overestimate.

The argument

Every candidate we record is a valid lower bound on a genuinely achievable score, so we never report something impossible. And the true optimum is reached: when the cursor lands on the optimal set's bottleneck, all its other elements were seen earlier, the heap holds at least as good a sum, and the minimum equals that bottleneck exactly. A lower bound everywhere, tight at the optimum ⟹ the max is correct. ∎

The general pattern

Where this approach shows up again

The general rule: when an objective couples two factors and one of them is a min or max over the chosen set, sort by that factor so it becomes predictable, then sweep while a heap manages the other. The min stops being circular once you fix the order in which you meet the elements.

“sum × min over a chosen k-subset”sort + heap

This problem. Sort by the min-factor descending; a size-k min-heap keeps the best sum.

“Max capital with k projects, each gated by a threshold”sort + heap

IPO (LC 502). Sort by the gate, unlock as you cross it, heap the payoff — same skeleton.

“Most points covered while a budget/efficiency holds”sort + heap

Sort events by the constraint axis; a heap evicts whatever no longer earns its place.

“K-th largest / smallest in a stream”size-k heap

The heap-of-size-k trick alone: keep exactly k, the root is your answer in O(log k).

“Two ratios / events that must both hold”sort one axis

Fix the harder dimension by sorting so it reads off monotonically, then greed the other.

“Trapping rain water, skyline, max area”bottleneck

The recurring idea: the answer is governed by a bottleneck — pin it, then optimize around it.

What trips people up

The traps that break naive code

Five things an interviewer will poke at — each one falls out of getting the sort direction and the heap size right.

sort descending, not ascending

You need the current element to be the smallest nums2 in the window, so it's a valid minimum. Sort nums2 descending. Ascending breaks the invariant silently.

evaluate only when the heap is full

A score is legal only once you hold exactly k elements. Reading sum × n2 with fewer than k in the heap counts a phantom selection.

overflow — it's ~10¹⁵

sum ≤ k·10⁵ and the min ≤ 10⁵, so the product reaches ~10¹⁵. In Java/C++ that's a long. Ruby's integers are unbounded, but say it out loud.

k = 1 is just max(nums1[i]·nums2[i])

With one pick there's no real min to manage. The machinery still gives it for free — heap of size 1 — but flag that you noticed the degenerate case.

pop by nums1, take the minimum from nums2

The heap orders by nums1 (evict the smallest contribution to the sum); the value you multiply by is the nums2 of the current element. Mixing the two keys is the classic bug.

zeros are allowed

nums1[i] can be 0 (dead weight you may be forced to take) and nums2 can be 0 (a minimum that zeroes the score). Both are valid inputs; the greedy handles them without special cases.

Quick reference

The interview cheat-sheet

“What's the approach?”

Sort pairs by nums2 descending. Sweep; push nums1 into a min-heap; if it exceeds k, pop the smallest and subtract. When the heap holds exactly k, sum × current nums2 is a candidate. O(n log n).

“Why descending?”

So the element you're standing on is the smallest nums2 of everything in the heap — a valid minimum for that group. Every later element only lowers the floor.

“Why a heap of nums1?”

Once the minimum is fixed, you just want the largest possible sum from the eligible pool — that's the top-k nums1, and a size-k min-heap maintains exactly that as you stream.

“Why isn't it wrong when the current element gets popped?”

Because sum × current_nums2 is never an overestimate — every element left in the heap has nums2 ≥ current, so the true score of that group is ≥ what you recorded. You can only under-count, and the real optimum still gets hit exactly when its bottleneck is the cursor.

“Don't forget…”

Only score when the heap is full (== k). The product can hit ~10¹⁵ (use 64-bit outside Ruby). k = 1 is the trivial max(nums1·nums2).

the whole solution · rubyO(n log n)

def max_score(nums1, nums2, k)

  # Pair them up, then sort so the nums2 we meet only shrinks.

  pairs = nums1.zip(nums2).sort_by { |_n1, n2| -n2 }

  heap = MinHeap.new   # holds nums1 values; smallest on top

  sum  = 0

  best = 0

  pairs.each do |n1, n2|

    heap.push(n1)

    sum += n1

    # Keep only the k largest nums1 seen so far.

    sum -= heap.pop if heap.size > k

    # Heap full -> n2 is the guaranteed minimum of this group.

    best = [best, sum * n2].max if heap.size == k

end

  best

end

Ruby ships no heap, so drop in a tiny binary MinHeap with push / pop / size (sift-up on insert, sift-down on remove). Everything else is the four lines inside the loop.

The summary

"The hard part is the min over a chosen set, so I make it predictable: sort by nums2 descending, and the element I'm on is always the minimum of everything before it. Then it's greedy — keep the k largest nums1 in a heap and read sum × current nums2 at every step. One sort, one sweep, O(n log n)."