Abstract / Summary

Given a list of numbers and a target k, find the maximum sum of a subsequence where no two chosen elements are within k positions of each other.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Heap (Priority Queue)
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of selecting exactly k elements from two parallel arrays, nums1 and nums2, so that the product of the smallest chosen value from nums2 and the sum of the corresponding chosen values from nums1 is maximized. The algorithm builds a mapping from each distinct value in nums2 to the list of associated nums1 values, then processes those groups in descending order of the nums2 key while maintaining a min-heap of the currently best k candidates from nums1. At each step where the heap reaches size k, it evaluates the candidate score and updates the best result seen so far.

Key Steps

Building the value groups

all = defaultdict(list)
for i in range(len(nums1)):
    all[nums2[i]].append(nums1[i])

A dictionary named all (a defaultdict of lists) is populated by iterating over the indices of the input arrays. For each index, the element from nums2 becomes a key, and the corresponding element from nums1 is appended to the list stored under that key. This groups together all nums1 values that share the same nums2 value, enabling the later stage to consider all candidates that would produce the same minimum multiplier.

Preparing the heap and accumulator

one   = []
total = 0
best  = 0

one is an empty list that will serve as a min-heap via the heapq interface. total holds the sum of the elements currently stored in the heap, and best records the highest score discovered during the scan.

Scanning groups in descending order

for mini in sorted(all, reverse = True):
    for m in all[mini]:
        heappush(one, m)
        total += m

        if len(one) == k:
            best = max(best, mini * total)
            total -= heappop(one)

The outer loop iterates over the distinct nums2 values (mini) sorted from largest to smallest. This ordering guarantees that, at any point, mini represents the smallest nums2 value among the elements that have been considered so far, because all larger keys have already been processed.

Inside the inner loop each m (a nums1 value associated with the current mini) is pushed onto the heap and added to total. The heap automatically keeps the smallest element at its root. When the heap size reaches k, the algorithm computes a candidate score as mini * total. This product reflects the scenario where the current mini is the limiting nums2 value and the sum of the k largest nums1 values seen up to this point is total. After evaluating the candidate, the smallest element in the heap is removed with heappop, and its value is subtracted from total. This removal prepares the heap for the next iteration, ensuring that it always contains the k largest nums1 values among those processed so far.

Returning the result

return best

After all groups have been examined, best holds the maximum achievable score and is returned as the final answer.

Edge Cases Handled

The algorithm naturally accommodates several boundary conditions without additional checks. When k equals the length of the input arrays, the heap will eventually contain every element, and the final iteration will compute the product using the smallest nums2 value across the whole dataset. If k is 1, the heap size condition triggers after each insertion, causing the algorithm to evaluate every single pair (nums1[i], nums2[i]) and select the maximum product of the two numbers. Duplicate values in nums2 are grouped together, so all corresponding nums1 entries are processed in the same iteration, preserving correctness when many elements share the same minimum multiplier. The use of defaultdict(list) ensures that missing keys never cause a KeyError, and the sorted traversal works even when the dictionary contains a single key.

Performance Optimizations

The code leverages a min-heap to keep track of the top k nums1 values seen so far. By pushing each candidate onto the heap and popping only when the heap exceeds size k, the algorithm avoids sorting the entire list of candidates, reducing the amount of work required to maintain the best subset. The running sum total is updated incrementally with each push and pop, eliminating the need to recompute the sum of the heap contents from scratch at every step. Sorting the distinct nums2 keys once, in descending order, provides a deterministic order that allows the algorithm to treat the current key as the minimum multiplier without additional comparisons. Together, these choices keep the core loop tight and avoid unnecessary data movement, leading to an efficient solution for large input sizes.

Imagine there are two lines of people at a party. The first line has people with big balloons and the second line has people with colorful hats. This code helps pick a small group of people from the first line so that the total size of their balloons multiplied by the number on the smallest hat chosen makes the biggest possible score.

First, the computer organizes everyone by looking at their hats and keeping track of which balloons go with which hats. It starts by looking at the people with the very biggest hats and works its way down to the people with the smallest hats.

As it looks through these hat groups, it adds the matching balloons into a special pile. This pile always keeps the biggest balloons at the ready. Once the pile grows to the size requested, the computer multiplies the total sum of all those chosen balloons by the hat number it is currently looking at. If that result is bigger than any other score found so far, it saves that number as the best one. Whenever the pile gets too full, it tosses out the smallest balloon from the group to make room for something better and keeps moving along until every hat has been checked.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++	Python		TS
	WalkCCC		Java	C++	Python
	leetcode.ca		Java	C++	Python	Go
	Progiez		Java	C++	Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	lkwq007				Python
	varunu28		Java
	wisdompeak			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality