Problem

Source: Codility

Given an array A of length n filled with integers find the smallest missing positive number.

Example:

[4,8,1,3,2] => 5

[1,2] =>3

Restrictions

• n ranges from 1 .. 100,000
• Values of A range from -1,000,000 to 1,000,000

My Solution

As usual, I decided to first take a brute force approach. As a result, I forced the array into a Set then iteratively checked each number sequentially from 1 to n+1.

function brute_force(A) {
    const aSet = new Set(A)
    for (let i = 1; i <= aSet.size + 1; i++) {
        if (!aSet.has(i)) {
            return i
        }
    }
}

This worked well. The next task was to think about how to make it work faster. The worst-case scenario would be all positive natural numbers from 1 to n with no missing numbers since we’d have to check every number.

I thought we could possibly squeeze a few milliseconds by reducing A to a positive only set but honestly, the constructor is plenty fast so there was no visible benefit. In the end, I didn’t find another way to get this to go faster so I decided to see how the brute-force method faired.

Turns out, very well. It passed all performance tests with flying colors. So I guess that’s that. 🤷