/*
Given an array of integers, find the first missing positive integer in linear time and constant space.
In other words, find the lowest positive integer that does not exist in the array.
The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.
*/
function findSmallestMissingPositiveInteger(arr) {
  // Il numero può essere al massimo arr.length + 1,
  // quando nell'array ci sono tutti e soli i numeri compresi tra 1 ed arr.length
  // in qualsiasi altro caso ci sarà un gap prima di tale valore.

  // Quindi possiamo scartare tutti i numeri al di fuori del range [1, arr.length], mettendoli a 0
  for (let i = 0; i < arr.length; ++i) {
    if (arr[i] < 1 || arr[i] > arr.length) {
      arr[i] = 0;
    }
  }

  // Adesso possiamo semplicemente ciclare e trattare i numeri come indici all'array stesso
  // e il principio di base è: esploro e marchio le celle come libera (0) o occupata (-1)
  for (let i = 0; i < arr.length; ++i) {
    // Ciclo finché non trovo il primo numero valido
    if (arr[i] !== 0 && arr[i] !== -1) {
      // Mi salvo il valore
      let curr = arr[i];
      // Marchio la cella come libera
      arr[i] = 0;

      while (true) {
        // Prendo il valore successivo
        let next = arr[curr - 1];
        // Segno la posizione come occupata
        arr[curr - 1] = -1;
        // Finchè la cella di destinazione non è già marchiata come libera (0) o occupata (-1)
        // devo continuare a propagare l'esplorazione seguendo la catena di indici
        // altrimenti non so dove mettere il valore appena estratto.
        if (next === 0 || next === -1) {
          break;
        }
        curr = next;
      }
    }
  }

  // Cerco la prima cella libera, che corrisponde al gap nella sequenza di valori
  for (let i = 0; i < arr.length; ++i) {
    if (arr[i] === 0) {
      return i + 1;
    }
  }

  // Se non ho trovato nessun gap la soluzione è il primo intero maggiore della lunghezza dell'array
  return arr.length + 1;
}