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:

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.
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.

Here some unit tests to check for correctness:

import kotlin.test.Test

class SmallestMissingIntegerTest {

    @Test
    fun `first missing positive 1`() {
        val result = firstMissingPositive(intArrayOf(1, 2, 0))
        assert(result == 3) { "Expected 3, but got $result" }
    }

    @Test
    fun `first missing positive 2`() {
        val input = intArrayOf(3, 4, -1, -21,1)
        val result = firstMissingPositive(input)
        checkResult(input, 2)
    }

    @Test
    fun `first missing positive 3`() {
        val input = intArrayOf(7, 8, 9, 11, 12)
        val result = firstMissingPositive(input)
        checkResult(input, 1)
    }

    @Test
    fun `first missing positive 4`() {
        val input = intArrayOf(1, 2, 3, 4,8)
        val result = firstMissingPositive(input)
        checkResult(input, 5)
    }

    @Test
    fun `first missing positive 5`() {
        val input = intArrayOf(4,2,1,8)
        val result = firstMissingPositive(input)
        checkResult(input, 3)
    }

    @Test
    fun `first missing positive 6`() {
        val input = intArrayOf(4,2,1,3,5)
        val result = firstMissingPositive(input)
        checkResult(input, 6)
    }


    private fun checkResult(nums: IntArray, expected: Int) {
        val result = firstMissingPositive(nums)
        assert(result == expected) { "Expected $expected, but got $result" }
    }
}

So What? Reflections

This problem is a classic example of how clever use of sorting algorithms can solve seemingly tricky problems efficiently. Cyclic sort may seem a bit obscure at first, but once you get the hang of it, it’s a powerful tool to have in your algorithm arsenal.

The beauty of this approach lies in its simplicity and efficiency. Just few lines of code and the trick of placing each number in its correct index, we transform the problem into a straightforward search for the first anomaly in the sorted sequence.

Why should we care?

Why should you care about finding the smallest missing positive integer or mastering cyclic sort?

For some time I thought, this were just abstract challenges, only there to make life harder in job interviews and coding challenges, providing little or no advantage in real-life problems. It turns out, they do have applications.

Efficiently managing and processing data is a critical aspect of many fields.

Here are a few examples where such algorithms can make a tangible difference:

Data Management: When dealing with large datasets, quickly identifying missing records or gaps can improve data integrity and consistency checks.
Inventory Management: Finding missing or unrecorded items in inventory systems can streamline operations and reduce losses.
Financial Systems: Detecting missing transactions or account entries.

This is a very general set of problems, no matter if the sequence of data are monitoring data coming from sensors, tracking of orders, ticket booking, invoice numbers etc… Sort the array as efficiently as you can, identify holes in the sequence, problem solved. Well at least identified :)

By honing these skills, you’re not just preparing for an interview — you’re equipping yourself to tackle real-world problems efficiently and effectively.

Keep practicing, and soon you’ll find these types of problems second nature. Happy coding! 🚀