TypeScript Find the lowest missing number in an array

How can we implement it if we want to get the lowest unused or missing number?

If the array starts with 0, it’s easy to implement it but how can we do that if it doesn’t start with 0? Furthermore, what if the incremented number is not 0?

The example arrays and the expected values are shown below.

const array = [0, 1, 2, 4, 5];          // 3
const array2 = [-3, -2, 0, 1, 2, 4, 5]; // -1
const array3 = [-1.5, -1.0, 0, 0.5];    // -0.5

Compare the index and the value

Using for loop

This is the simplest way.

function findLowestUnusedNumber(numbers: number[]): number {
    for (let i = 0; i < numbers.length; i++) {
        if (i !== numbers[i]) {
            return i;
        }
    }
    return numbers.length;
}

console.log(findLowestUnusedNumber([0, 1, 2, 4, 5]));           // 3 -> OK
console.log(findLowestUnusedNumber([0, 1, 2, 3, 4, 5]));        // 6 -> OK
console.log(findLowestUnusedNumber([0, 1, 1, 2, 4, 5]));        // 2 -> NG
console.log(findLowestUnusedNumber([0, 1, 2, 5]));              // 3 -> OK
console.log(findLowestUnusedNumber([-3, -2, 0, 1, 2, 4, 5]));   // 0 -> NG
console.log(findLowestUnusedNumber([-1.5, -1.0, 0, 0.5]));      // 0 -> NG
console.log(findLowestUnusedNumber([-1.5, -1.0, -0.5, 0, 0.5, 1.0]));// 0 -> NG

It compares the index and the value. This way can be used only for an array that starts with 0 and the value is incremented one by one.

As you can see, the first two cases are correct. If there are duplicates in it, or starts with a non-zero value, it doesn’t work.

Using find method

For the simple array, we can implement it without for loop. Use find method instead but the found value is not always one bigger. It returns an incorrect value for the 4th array too.

function findLowestUnusedNumber1(numbers: number[]): number {
    const result = numbers.find((value, index) => value !== index);
    if (result) {
        return result - 1;
    }
    return numbers.length;
}
console.log(findLowestUnusedNumber1([0, 1, 2, 4, 5]));   // 3 -> OK
console.log(findLowestUnusedNumber1([0, 1, 2, 3, 4, 5]));// 6 -> OK
console.log(findLowestUnusedNumber1([0, 1, 1, 2, 4, 5]));// 0 -> NG
console.log(findLowestUnusedNumber1([0, 1, 2, 5]));      // 4 -> NG
console.log(findLowestUnusedNumber1([-3, -2, 0, 1, 2, 4, 5]));  // -4 -> NG
console.log(findLowestUnusedNumber1([-1.5, -1.0, 0, 0.5]));     // -2.5 -> NG
console.log(findLowestUnusedNumber1([-1.5, -1.0, -0.5, 0, 0.5, 1.0]));// -2.5 -> NG

To solve the problem, use index instead of value.

function findLowestUnusedNumber1_2(numbers: number[]): number {
    let foundIndex;
    const result = numbers.find((value, index) => {
        if (value !== index) {
            foundIndex = index;
            return true;
        }
        return false;
    });
    if (foundIndex) {
        return foundIndex;
    }
    return numbers.length;
}
console.log(findLowestUnusedNumber1_2([0, 1, 2, 4, 5]));   // 3 -> OK
console.log(findLowestUnusedNumber1_2([0, 1, 2, 3, 4, 5]));// 6 -> OK
console.log(findLowestUnusedNumber1_2([0, 1, 1, 2, 4, 5]));// 2 -> NG
console.log(findLowestUnusedNumber1_2([0, 1, 2, 5]));      // 3 -> OK
console.log(findLowestUnusedNumber1_2([-3, -2, 0, 1, 2, 4, 5]));// 7 -> NG
console.log(findLowestUnusedNumber1_2([-1.5, -1.0, 0, 0.5]));     // 4 -> NG
console.log(findLowestUnusedNumber1_2([-1.5, -1.0, -0.5, 0, 0.5, 1.0]));// 6 -> NG

This function still doesn’t return the correct value for an array that has duplicates.

Remove duplicates by Set and compare the value and index

If the array has duplicates, they need to be removed. You can check the following post to know how to implement duplicates.

We use Set in this example.

function findLowestUnusedNumber2(numbers: number[]): number {
    const numberSet = new Set(numbers);

    let count = 0;
    for (const value of numberSet.values()) {
        if (count !== value) {
            return count;
        }
        count++;
    }
    return numberSet.size;
}

console.log(findLowestUnusedNumber2([0, 1, 2, 4, 5]));          // 3 -> OK
console.log(findLowestUnusedNumber2([0, 1, 2, 3, 4, 5]));       // 6 -> OK
console.log(findLowestUnusedNumber2([0, 1, 1, 2, 2, 4, 5]));    // 3 -> OK
console.log(findLowestUnusedNumber2([0, 1, 2, 5]));             // 3 -> OK
console.log(findLowestUnusedNumber2([-3, -2, 0, 1, 2, 4, 5]));  // 0 -> NG
console.log(findLowestUnusedNumber2([-1.5, -1.0, 0, 0.5]));     // 0 -> NG
console.log(findLowestUnusedNumber2([-1.5, -1.0, -0.5, 0, 0.5, 1.0]));// 0 -> NG

This function can’t handle an array that starts with non-zero.

Set start value and step to handle most cases

The last function can handle most cases.

function findLowestUnusedNumber3(numbers: number[], step = 1): number {
    const numberSet = new Set(numbers);

    let currentExpected = numbers[0];
    for (const value of numberSet.values()) {
        if (currentExpected !== value) {
            return currentExpected;
        }
        currentExpected += step;
    }
    return numbers[numbers.length - 1] + step;
}

console.log(findLowestUnusedNumber3([0, 1, 2, 4, 5]));          // 3 -> OK
console.log(findLowestUnusedNumber3([0, 1, 2, 3, 4, 5]));       // 6 -> OK
console.log(findLowestUnusedNumber3([0, 1, 1, 2, 2, 4, 5]));    // 3 -> OK
console.log(findLowestUnusedNumber3([0, 1, 2, 5]));             // 3 -> OK
console.log(findLowestUnusedNumber3([-3, -2, 0, 1, 2, 4, 5]));  // -1 -> OK
console.log(findLowestUnusedNumber3([-1.5, -1.0, 0, 0.5], 0.5));// -0.5 -> OK
console.log(findLowestUnusedNumber3([-1.5, -1.0, -0.5, 0, 0.5, 1.0], 0.5));// 1.5 -> OK

We used index before but the lowest value is used here. Then, it is incremented by the value specified in the parameter.

We can handle most cases in this way. If you need to handle smaller numbers, this function might not work due to a rounded-off error.

But I think there is likely no such case in real.

Note that the array needs to be sorted first if it’s not sorted.

console.log([5, 1, 2, 6, 3, 8, 9].sort())
// [ 1, 2, 3, 5, 6, 8, 9 ]