#2542 - Maximum Subsequence Score

MediumHeap / Priority Queue

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose k indices. The score is (sum of selected nums1 values) × (minimum of selected nums2 values). Return the maximum possible score.

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

Solution Space

Try it

/**
 * Maximizes (sum of k selected nums1 values) × (min of their nums2 values).
 *
 * Strategy: sort by nums2 descending so each candidate becomes the new minimum.
 * Maintain a min-heap of size k over nums1 values to keep the largest k sums.
 *
 * @param nums1 First array
 * @param nums2 Second array (determines the minimum factor)
 * @param k     Number of indices to select
 * @returns     Maximum score
 */
export function maxScore(nums1: number[], nums2: number[], k: number): number {
  const n = nums1.length;

  // Pair and sort by nums2 descending
  const indices = Array.from({ length: n }, (_, i) => i);
  indices.sort((a, b) => nums2[b] - nums2[a]);

  // Min-heap for nums1 values (using sorted array for clarity)
  const heap: number[] = [];
  let sum = 0;
  let maxScore = 0;

  for (const idx of indices) {
    const val1 = nums1[idx];
    const val2 = nums2[idx];

    heap.push(val1);
    heap.sort((a, b) => a - b);
    sum += val1;

    // Once heap exceeds k, remove the smallest nums1 value
    if (heap.length > k) {
      sum -= heap.shift()!;
    }

    // Only compute score when we have exactly k elements
    if (heap.length === k) {
      // val2 is the current minimum because we sorted nums2 descending
      maxScore = Math.max(maxScore, sum * val2);
    }
  }

  return maxScore;
}

Approach: greedy sort + min-heap – sort pairs by `nums2` descending. Iterate: each element becomes the candidate minimum. Maintain a size-k min-heap of `nums1` values to maximise the sum. Score = `sum × currentNums2`.

Time: O(n log n) for sorting + O(n log k) with a proper heap.

Space: O(n) – for the index array and heap.

#2462 Total Cost to Hire K Workers

#162 Find Peak Element