fnfirst_missing_positive(numbers:&mut[isize])->isize{lettarget_range=1..=(numbers.len()asisize);foriin0..numbers.len(){loop{if!target_range.contains(&numbers[i]){break;// target cannot be moved}letcorrect_place=numbers[i]asusize-1;ifnumbers[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)asisize==number{None}else{Some(i+1)}}).unwrap_or_else(||numbers.len()+1)asisize}

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.

For further actions, you may consider blocking this person and/or reporting abuse

We're a place where coders share, stay up-to-date and grow their careers.

Here is my solution in Rust:

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:

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.