Introduction

The phrase "smallest integer not in a list" sounds simple, but it needs one extra assumption. If the list may contain any integers, then the problem has no answer, because there is always a smaller missing negative number.

In practice, this question almost always means "find the smallest positive integer not present in the list." Once that is clear, there are two standard solutions: a simple set-based approach and an in-place linear-time approach.

Clarify the Problem First

Suppose the list is [1, 2, 4, 5]. The smallest positive integer missing from the list is 3.

Suppose the list is [0, -1, 2]. The smallest positive integer missing from the list is 1, because values less than 1 do not matter for this version of the problem.

That positive-only assumption is what makes the problem well-defined and useful in interviews and production code alike.

Simple and Readable Set-Based Solution

The easiest correct solution is to place the values in a set, then count upward from 1 until you find a number that is not present.

1def smallest_missing_positive(nums: list[int]) -> int:
2    seen = set(nums)
3    candidate = 1
4
5    while candidate in seen:
6        candidate += 1
7
8    return candidate
9
10
11print(smallest_missing_positive([1, 2, 4, 5]))      # 3
12print(smallest_missing_positive([3, 4, -1, 1]))     # 2
13print(smallest_missing_positive([7, 8, 9, 11, 12])) # 1

This runs in O(n) average time because set lookup is constant time on average, and it uses O(n) extra memory for the set.

For most real applications, this is the best solution. It is short, easy to review, and hard to get wrong.

In-Place O(n) Time and O(1) Extra Space

If you need the classic interview-optimized solution, you can use the array itself to track which values from 1 through n are present. The general idea is:

1. Ignore numbers that are non-positive or greater than n.
2. Use index positions to mark which positive values exist.
3. Scan for the first index that was never marked.

Here is a working Python implementation:

1def smallest_missing_positive_in_place(nums: list[int]) -> int:
2    n = len(nums)
3
4    has_one = 1 in nums
5    if not has_one:
6        return 1
7
8    for i in range(n):
9        if nums[i] <= 0 or nums[i] > n:
10            nums[i] = 1
11
12    for i in range(n):
13        value = abs(nums[i])
14        index = value - 1
15        if nums[index] > 0:
16            nums[index] = -nums[index]
17
18    for i in range(n):
19        if nums[i] > 0:
20            return i + 1
21
22    return n + 1
23
24
25print(smallest_missing_positive_in_place([3, 4, -1, 1]))  # 2
26print(smallest_missing_positive_in_place([1, 2, 0]))      # 3

Why does this work? In a list of length n, the smallest missing positive integer must be in the range from 1 through n + 1. If every value from 1 through n is present, then the answer is n + 1. Otherwise, the first missing value inside that range is the answer.

When Sorting Is Acceptable

Another reasonable approach is to sort the numbers, then scan for the first gap. That is easy to understand but costs O(n log n) time:

1def smallest_missing_positive_sorted(nums: list[int]) -> int:
2    candidate = 1
3
4    for value in sorted(set(nums)):
5        if value < candidate:
6            continue
7        if value == candidate:
8            candidate += 1
9        elif value > candidate:
10            break
11
12    return candidate

This can be perfectly fine when input sizes are small or clarity matters more than asymptotic optimality.

Common Pitfalls

• Forgetting to define the domain. Without the "positive integer" restriction, the problem is not well-posed.
• Starting from 0 instead of 1 when the expected answer is the smallest missing positive integer.
• Failing on duplicates such as [1, 1, 2, 2]. A correct algorithm must handle repeated values cleanly.
• Mishandling negative numbers or zeros. They should be ignored for the positive-only version.
• Choosing the in-place algorithm when readability matters more than minimizing memory usage.

Summary

• The meaningful version of this problem is usually "smallest missing positive integer."
• A set-based solution is the simplest correct O(n) approach for most codebases.
• The in-place marking algorithm also runs in O(n) time and uses constant extra space.
• Sorting is easier to reason about but slower on large inputs.
• Before writing code, make sure the problem statement is precise enough to have a real answer.