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.

LeetCode 2336 Smallest Number in Infinite Set – JavaScript

What looks like an infinite-data-structure problem becomes much simpler once we notice that we do not need to store the entire infinite set. In this LeetCode 2336 Smallest Number in Infinite Set solution, we use a JavaScript Set to remember numbers that were added back and a current pointer to represent the untouched part of the infinite sequence.

The key idea is to separate the numbers that have been removed and later returned from the numbers that have never been removed. This lets us simulate the infinite set without actually creating it.

Problem Statement

LeetCode 2336, Smallest Number in Infinite Set, asks us to implement a data structure that initially contains every positive integer:

1, 2, 3, 4, 5, 6, ...

We need to support two operations:

• popSmallest() removes and returns the smallest number currently available.
• addBack(num) adds a number back if it is no longer present in the set.

You can read the original problem on LeetCode 2336 – Smallest Number in Infinite Set .

Problem Number: 2336
Difficulty: Medium
Topics: Set, Design, Heap / Priority Queue

Examples

Example 1

Input:

["SmallestInfiniteSet", "addBack", "popSmallest",
 "popSmallest", "popSmallest", "addBack",
 "popSmallest", "popSmallest", "popSmallest"]

[[], [2], [], [], [], [1], [], [], []]

Output:

[null, null, 1, 2, 3, null, 1, 4, 5]

Calling addBack(2) does nothing because 2 is already present. After removing 1, 2, and 3, calling addBack(1) makes 1 available again, so the next smallest value is 1.

Example 2

Simple sequence:

popSmallest() → 1
popSmallest() → 2
popSmallest() → 3
addBack(2)
popSmallest() → 2
popSmallest() → 4

Once 2 is added back, it becomes smaller than the next untouched number, 4, so it must be returned first.

Constraints

• 1 <= num <= 1000
• At most 1000 calls are made to popSmallest and addBack in total.

These constraints are important. Although the conceptual set is infinite, only a limited number of operations can happen. Therefore, we never need to explicitly store the entire infinite set.

Key observation: After at most 1000 operations, only a limited number of values can have been removed and added back. We can track those exceptional values instead of representing infinity.

Intuition

Imagine the infinite set as two parts:

Numbers added back   |   Untouched numbers

For example, suppose we have already removed 1, 2, 3, and 4.

The next untouched number is 5. We can represent that with:

current = 5

Now suppose addBack(2) is called. We do not need to move current backward. We simply remember that 2 has become available again:

heap = {2}
current = 5

The smallest available number is now 2. After returning 2, the Set becomes empty, so the next call can return current, which is 5.

This is exactly what the two variables in the solution represent:

• current represents the smallest number that has never been removed.
• heap stores numbers that were removed earlier and subsequently added back.

Approach

Brute-Force Idea

One straightforward idea would be to explicitly store many positive integers and repeatedly search for the smallest available value.

The problem is that the set is conceptually infinite. Storing every positive integer is neither necessary nor practical.

We only need to keep track of numbers that differ from the normal increasing sequence.

Step-by-Step Approach

1. Initialize current = 1.
2. Maintain a Set called heap for numbers that have been added back.
3. In popSmallest(), if the Set contains numbers, find its smallest number, remove it, and return it.
4. If the Set is empty, return current and increment it.
5. In addBack(num), only add num when num < current.

Why does the condition num < current work?

Any number greater than or equal to current has not been removed yet. Therefore, it is already present in the infinite set and does not need to be added back.

For example, if current = 5, then 5, 6, 7, 8, ... are already available. Calling addBack(7) would make no difference.

Dry Run

Let's trace the main example while tracking both pieces of state.

Step	Operation	heap	current	Result
1	addBack(2)	{}	1	No change
2	popSmallest()	{}	2	1
3	popSmallest()	{}	3	2
4	popSmallest()	{}	4	3
5	addBack(1)	{1}	4	1 added
6	popSmallest()	{}	4	1
7	popSmallest()	{}	5	4
8	popSmallest()	{}	6	5

Notice the important transition at addBack(1). The current pointer remains at 4 because the untouched sequence still starts from 4. The value 1 is handled separately through the Set.

LeetCode 2336 Smallest Number in Infinite Set Solution in JavaScript

Here is the submitted JavaScript solution exactly as provided:

JavaScript Solution

var SmallestInfiniteSet = function () {

    this.heap = new Set();

    this.current = 1;

};

/**

 * @return {number}

 */

SmallestInfiniteSet.prototype.popSmallest = function () {

    if (this.heap.size > 0) {

        let smallest = Infinity;

        for (let num of this.heap) {

            smallest = Math.min(smallest, num);

        }

        this.heap.delete(smallest);

        return smallest;

    }

    return this.current++;

};

/**

 * @param {number} num

 * @return {void}

 */

SmallestInfiniteSet.prototype.addBack = function (num) {

    if (num < this.current) {

        this.heap.add(num);

    }

};

Code Walkthrough

1. Tracking numbers added back

this.heap = new Set();

Despite its variable name, heap is not a heap. It is a JavaScript Set.

Its purpose is to store numbers that have previously been removed and then added back. The Set also automatically prevents duplicates.

2. Tracking the untouched sequence

this.current = 1;

current starts at 1 because 1 is initially the smallest number.

Whenever there are no added-back numbers waiting in the Set, the next smallest number is simply current.

3. Finding the smallest added-back number

let smallest = Infinity;

for (let num of this.heap) {
    smallest = Math.min(smallest, num);
}

JavaScript's standard Set does not automatically provide the minimum element. Therefore, when the Set contains values, the solution scans through them and keeps the smallest value found.

This is the main reason the actual time complexity of this solution is O(k) for this case, rather than O(log k) as it would be with a real min-heap.

4. Removing the selected number

this.heap.delete(smallest);
return smallest;

Once the smallest added-back number is found, it is removed from the Set because popSmallest() must remove the returned number from the set.

5. Moving through untouched numbers

return this.current++;

If there are no added-back numbers, the next smallest number comes from the untouched sequence.

The post-increment returns the current value and then moves the pointer forward by one.

6. Adding a number back

if (num < this.current) {
    this.heap.add(num);
}

This condition is the key to avoiding unnecessary entries.

If num < current, that number has already been passed by the pointer and therefore could have been removed. It may genuinely need to be added back.

If num >= current, the number is already part of the untouched infinite sequence, so adding it again would not change anything.

Complexity Analysis

Time Complexity

popSmallest() with a non-empty Set: O(k), where k is the number of values currently stored in the Set, because the code scans every value to find the minimum.

popSmallest() with an empty Set: O(1), because it simply returns current and increments it.

addBack(): O(1) average, because JavaScript Set insertion is expected constant time.

With at most 1000 total operations, the maximum Set size is bounded by the problem's operation limit, so this implementation is fast enough for the given constraints.

Space Complexity

O(k), where k is the number of currently stored added-back values. The solution does not store the infinite set itself.

Edge Cases

• Calling addBack() on a number that was never removed: If the number is greater than or equal to current, it is already available, so nothing is added.
• Adding the same number multiple times: JavaScript's Set automatically prevents duplicate entries.
• Multiple numbers added back: The solution scans all values and returns the smallest one.
• Empty Set: When there are no added-back numbers, current supplies the next smallest value.
• Added-back number smaller than current: It must be returned before the untouched sequence because it is smaller than current.

Common Mistakes and Tips

• Do not try to create the infinite set. Track only the part of the state that can change.
• Do not add numbers that are already present. The num < current check handles this.
• Remember that JavaScript Set is not a min-heap. Finding the minimum requires iteration.
• Use Set semantics to handle duplicate add-back operations. A number should not appear multiple times in the stored collection.

FAQ

Why do we need the current pointer?

The pointer represents the smallest positive integer that has never been removed. Instead of storing all untouched numbers, we simply generate them one at a time using current++.

Why does addBack only store numbers smaller than current?

Numbers greater than or equal to current are still part of the untouched infinite sequence. Only numbers below current could have previously been removed and therefore need to be tracked separately.

Is the Set really a heap in this JavaScript solution?

No. The variable is named heap, but its actual type is Set. The code finds the minimum by iterating through the Set, which gives O(k) time for that operation.

Related Problems

• 41. First Missing Positive
• 1942. The Number of the Smallest Unoccupied Chair
• 2336. Smallest Number in Infinite Set
• 902. Numbers At Most N Given Digit Set

Conclusion

The main lesson from this problem is that an infinite data structure does not necessarily require infinite storage. We only need to represent the numbers that have deviated from the normal increasing sequence.

The current pointer handles untouched numbers, while the Set remembers numbers that have been added back. When the Set is non-empty, we search it for the smallest value; otherwise, we continue from current.

This LeetCode 2336 Smallest Number in Infinite Set solution is particularly useful for learning how to represent an infinite sequence with a small amount of state and how a simple Set can be sufficient when the constraints are small.