Smallest Missing Positive Integer Problem

Hey there 👋

this morning, while still enjoying my vacation from work, I thought to practice a bit and discovered this problem: the Smallest Missing Positive Integer problem, which can be formulated as follows:

Imagine you’re given an unsorted array of integers (they can be both positive or negative). Can you find the smallest positive integer, not present in the array?

Example: input: [2,7,-1,1] — the solution would be 3 since 1 and 2 are already in the array

Example2: input [8,9,10,11,12] — the solution would be 1, being the smallest positive integer not present in the original array.

Ideally you should implement a solution with time complexity O(n) and constant (O(1)) auxiliary space.

It’s a classic of Leetcode challenges and interview questions, but it was the first time for me to solve it, and since with my company we switched to Kotlin some months ago, I thought to try to solve it.

Let’s see how to do it…

The Intuition

The inportant piece of information here is to solve in O(n) with max. O(1) auxiliary space. This is an important constraint that usually means — translated — :

Hash maps and extra arrays are cool, but you’re not allowed to use them here.

So, what can we use? The trick here is to use Cyclic Sorting, which indeed operates in O(n) complexity together with a clever index placement. Since we’re searching for the smallest positive integer, we can just try to sort the elements so that they try to match their indices, and then see if a number was skipped in the placement (a number was missing between 1..n , n being the size of the array). Et voilà we have our smallest positive integer.

If not, since the array will be sorted, the number we’re searching for will simply be length + 1 , which intuitively makes sense.

Step by step solution

Let’s see cyclic sorting in action. The solution is pretty compact (one of the reasons to love Kotlin):

fun firstMissingPositive(nums: IntArray): Int {
    // Step 1 - Sort
    nums.cyclicSort()

    // Step 2: Find the first missing positive integer
    val missingInt = nums.indices.find { nums[it] != it + 1 }?.plus(1)

    return missingInt ?: nums.size.plus(1)
}

// Extension function - cyclic sort implementation
fun IntArray.cyclicSort() {
    this.forEachIndexed { index, _ ->
        while (this[index] in 1..this.size && this[this[index] - 1] != this[index]) {
            val correctIndex = this[index] - 1
            this[index] = this[correctIndex].also {
                this[correctIndex] = this[index]
            }
        }
    }
}

The solution consists of 2 simple steps:

1. Cyclic sorting the original array: We iterate through each element; if the element is in the range [1,nums.size] and not in the correct position, we swap indices (current vs. expected one). If not, keep the order as it is.
2. Find the missing integer: Now we have the array sorted in place, we expect something like this:

Original array: [4,2,1,8] Sorted array: [1,2,4,8], with 1 at the first position, 2at the second position, 3… not ath the 3rd position, as it is missing; the 3rd index has 4. In this way we identified the smallest possible missing integer: 3

If the array was complete, we would have a situation like this:

Original array: [4,2,1,3,5] Sorted array: [1,2,3,4,5]

Hence the smallest possible integer is simply nums.size + 1 , the size of the array + 1. And this is exactly what the code above does.

So What?

For a while I genuinely thought problems like this existed only to make interviews more stressful. Leetcode as ritual humiliation. A filter mechanism dressed up as skill assessment. That was too cynical.

The underlying pattern: place things where they belong, scan for the gap, does show up in real work, though rarely wearing the same clothes. Sequence integrity checks in data pipelines. Gap detection in invoice numbering. Time-series holes that break a nightly report. The specific algorithm doesn’t transfer verbatim; the mental model does. Sort in place, exploit the index, look for the anomaly.

Kotlin makes the expression of it almost pleasant. The .also idiom for the in-place swap is one of those small language features that feels like it was designed by someone who actually writes code day to day.