Ricerca in tempo lineare e spazio costante in array [Difficile]

Pubblicato il da Luca

Questo problema è stato chiesto da Stripe.

Data una matrice di numeri interi, trova il primo intero positivo mancante nel tempo lineare e nello spazio costante. In altre parole, trova l’intero positivo più basso che non esiste nell’array. L’array può contenere anche duplicati e numeri negativi.

Ad esempio, l’input [3, 4, -1, 1] dovrebbe dare 2. L’input [1, 2, 0] dovrebbe dare 3.

È possibile modificare l’array di input sul posto.