Discussion on: Daily Coding Problem #4

[Idan Arye]

Here is my solution in Rust:

fn first_missing_positive(numbers: &mut [isize]) -> isize {
    let target_range = 1..=(numbers.len() as isize);
    for i in 0..numbers.len() {
        loop {
            if !target_range.contains(&numbers[i]) {
                break; // target cannot be moved
            }
            let correct_place = numbers[i] as usize - 1;
            if numbers[correct_place] == numbers[i] {
                break; // correct place already contains a duplicate of that number
                // NOTE: this may also mean that our number is already at the correct place, and is
                // its own duplicate.
            }
            numbers.swap(i, correct_place);
        }
    }
    numbers.iter().copied().enumerate()
        .find_map(|(i, number)| {
            if (i + 1) as isize == number {
                None
            } else {
                Some(i + 1)
            }
        })
        .unwrap_or_else(|| numbers.len() + 1) as isize
}

Being allowed to modify the input array is a key hint, and my solution utilizes this to semi-sort the array. I swap every number I encounter to it's "correct" place - it's 1-based index. If that index is outside the range of the array, or the array already has a duplicate of that number in that position, I don't move it. When I do swap, I check again the number I've swapped with, and swap it as well if necessary. I do this until I reach a number that I don't swap - and then I move to the next cell in the array.

Note that I check each number at least once. If it wasn't swapped before I reach it, then I check it when I reach it. And if it was swapped - I check it after the swap (I may also check it again if I encounter it)

After this phase, each cell will contain it's "correct" number if and only if that number was in the original input:

• If the number was not in the original input, it won't be anywhere in the array - because we are just swapping cells so the resulting array is a permutation of the original one.
• If the number was in the original input, then at some point we have reached it and swapped it with this cell - unless that cell already had that number.

So, all that's left is to iterate through the array and return the 1-based index of the first cell that does not contain the "correct" number. If there is no such cell, that means that the original input had all the numbers from 1 to N and thus we return N + 1.

Space complexity is constant, because we did not use any collection (other than the original array, which we were allowed to modify)

Linear time complexity is a bit trickier to prove, because in the first iteration we are spending O(N) on each cell (at worst case we can do N swaps with the first cell). But this is amortized - after each swap one cell gets its "correct" number, and after that we no longer swap with or from that cell. This gives us O(N) swaps - each constant time, together with the check we do before it - plus O(N) for N constant checks that result in no swap (we advance to the next cell once we do a check that does not result in a swap), plus another O(N) for doing the second pass on the modified array to find the missing number = linear time.