Abstract / Summary

Given a list of integers and an integer k, append k non-negative integers to the list to make its sum minimal.

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 27% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Math
• 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 computes the smallest possible sum of k distinct positive integers that are not present in the input list nums. It does this by conceptually extending the natural number sequence while skipping any values that already appear in nums. The algorithm first removes duplicate entries, then iterates through the sorted unique values, expanding a running upper bound (limit) whenever a value falls within the current range. The final result is derived from the arithmetic series formula, subtracting the sum of the skipped numbers.

Key Steps

The core logic can be divided into three conceptual phases: preparation, range extension, and final calculation.

Preparation

limit = k
skip  = 0
for n in sorted(set(nums)):

The code begins by initializing limit to k, representing the tentative highest integer that might be needed to reach k distinct values. The variable skip accumulates the total of numbers that must be omitted because they already exist in nums. Converting nums to a set eliminates duplicates, and sorting the set ensures that the numbers are processed in ascending order, which is essential for the subsequent range-extension logic.

Range Extension

    if n <= limit:
        limit += 1
        skip  += n
    else:
        break

During the iteration, each unique number n is examined. If n lies within the current inclusive range [1, limit], it means that n would have been counted in the naive sum of the first limit natural numbers. To keep the sum exclusive of n, the algorithm expands the range by incrementing limit-effectively reserving the next unused integer for the final sum. Simultaneously, skip is increased by n to record the amount that must be subtracted later. The moment a number exceeds limit, the loop terminates because all subsequent numbers are guaranteed to be larger than any value that could affect the first limit natural numbers.

Final Calculation

return limit * (limit + 1) // 2 - skip

After the loop, the sum of the first limit positive integers is computed using the closed-form arithmetic series expression. Subtracting skip yields the sum of the smallest k positive integers that are not present in nums. This expression directly produces the desired result without needing to construct the actual list of missing numbers.

Edge Cases Handled

When nums contains values that are all larger than k, the loop never enters the if branch, leaving limit unchanged. The final formula then correctly returns the sum of the first k natural numbers, because no numbers need to be skipped.

If nums includes the integer 1, the algorithm detects that 1 falls within the initial range, increments limit to k+1, and adds 1 to skip. This adjustment ensures that the smallest missing integer starts from 2 instead of 1.

When nums contains a dense block of consecutive numbers starting from 1 (for example, [1,2,3,4] with k=3), each of those numbers triggers the range-extension step, pushing limit forward for each occurrence. The loop continues until it encounters a number outside the current range, guaranteeing that the final sum excludes all blocked values and includes the next available integers.

If nums is empty, the set conversion yields an empty collection, the loop body never executes, and the function returns the sum of the first k natural numbers, which is the correct minimal sum in the absence of any constraints.

Duplicate entries in nums are neutralized by the set conversion, preventing the same number from being counted multiple times in skip. This ensures that the algorithm’s arithmetic remains consistent regardless of repetition in the input.

Performance Optimizations

The most notable optimization is the elimination of duplicate values before sorting. By converting nums to a set, the algorithm reduces the number of elements that need to be processed, which directly lowers the cost of the subsequent sort operation.

Sorting the unique values once enables a single linear pass to adjust limit and skip. The early-exit condition (break) stops the iteration as soon as a number exceeds the current limit, avoiding unnecessary comparisons for the remainder of the sorted list.

The final sum is obtained through a constant-time arithmetic formula rather than iterating over each integer up to limit. This eliminates any need for explicit construction of the missing-number list, keeping both time and memory usage minimal.

Overall, the combination of deduplication, sorted traversal with early termination, and closed-form arithmetic yields an implementation that scales efficiently with the size of the input while maintaining a compact memory footprint.

Imagine you have a magical toy box that needs to be filled with the smallest numbers you can find, starting with the number one. You already have some numbers inside your box, but you want to pick new ones that are not in there yet.

The computer looks at all the numbers you already have and lines them up from smallest to biggest so it can see them clearly. It goes through these numbers one by one to see if they are small enough to be useful. If a number is small, the computer keeps it in a special group and decides to look for an even bigger number to fill the spot instead. It keeps track of all the numbers that are already taken so it does not count them again.

Once the computer finishes checking the numbers, it knows exactly how many total spots you need to fill your box with small, happy numbers. It calculates the sum of all the numbers in a perfect sequence from one up to the final number it found. Because some of those numbers were already in your box, the computer takes those away so everything is perfect.

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	C++	Java	Python				TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python			Go	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	fsq	C++
	JoshCrozier				JS
	lkwq007			Python
	suxrobGM					C#
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

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