4 marzo 2025

Due Puntatori

Nel campo della progettazione di algoritmi, la tecnica dei 2 Puntatori si distingue come un approccio potente e versatile per risolvere una varietà di problemi. Dalla manipolazione di array all’elaborazione di stringhe, questo metodo aiuta a ottimizzare sia la complessità temporale che quella spaziale rispetto a soluzioni più ingenue. Che tu stia preparando colloqui di programmazione o affinando le tue capacità di problem-solving, comprendere questa tecnica è fondamentale.

Cos’è la Tecnica dei Due Puntatori?

Alla sua base, la tecnica dei 2 Puntatori prevede l’uso di due indici (o puntatori) che attraversano una struttura dati, come un array, una stringa o una lista collegata, spesso partendo da estremi opposti o a velocità diverse. La strategia consiste nell’esaminare simultaneamente gli elementi in modo da ridurre il lavoro ridondante e diminuire il numero di iterazioni necessarie.

Varianti Comuni

Come Funziona

La forza di questa tecnica si trova nella sua semplicità ed efficienza:

Un chiaro esempio di questa tecnica

Un esempio chiaro di questa tecnica è la sua applicazione nella ricerca di due numeri in un array ordinato che sommino a una somma target. Con un puntatore all’inizio e uno alla fine, puoi individuare rapidamente la coppia corretta senza dover verificare ogni possibile combinazione.

Esempi

Questo metodo ha trovato applicazione in diverse sfide algoritmiche classiche:

1. Trovare Coppie con una Data Somma

Dato un array ordinato, trovare due numeri che sommati ottengano il valore target.

function twoSumSorted(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    let sum = arr[left] + arr[right];

    if (sum === target) {
      return [arr[left], arr[right]]; // Found the pair
    } else if (sum < target) {
      left++; // Move left pointer to increase sum
    } else {
      right--; // Move right pointer to decrease sum
    }
  }

  return []; // No valid pair found
}

// Example usage:
console.log(twoSumSorted([1, 2, 3, 4, 6], 6)); // Output: [2, 4]

Efficienza

2. Unire Array Ordinati

Dati due array ordinati, unirli in un singolo array ordinato in tempo O(n + m).

function mergeSortedArrays(arr1, arr2) {
  let i = 0;
  let j = 0;
  let mergedArray = [];

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      mergedArray.push(arr1[i]);
      i++; // Move pointer in arr1
    } else {
      mergedArray.push(arr2[j]);
      j++; // Move pointer in arr2
    }
  }

  // Add remaining elements from arr1 (if any)
  while (i < arr1.length) {
    mergedArray.push(arr1[i]);
    i++;
  }

  // Add remaining elements from arr2 (if any)
  while (j < arr2.length) {
    mergedArray.push(arr2[j]);
    j++;
  }

  return mergedArray;
}

// Example usage:
console.log(mergeSortedArrays([1, 3, 5, 7], [2, 4, 6, 8]));
// Output: [1, 2, 3, 4, 5, 6, 7, 8]

Efficienza

3. Rimuovere Duplicati

Quando ci occupiamo di array ordinati, possiamo rimuovere i duplicati in tempo O(n) usando la tecnica dei Due Puntatori.

function removeDuplicates(arr) {
  if (arr.length === 0) return 0;

  let uniqueIndex = 0; // This pointer keeps track of the unique elements

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[uniqueIndex]) {
      uniqueIndex++;
      arr[uniqueIndex] = arr[i]; // Move unique element to the front
    }
  }

  return arr.slice(0, uniqueIndex + 1); // Return the unique elements
}

// Example usage:
console.log(removeDuplicates([1, 1, 2, 2, 3, 4, 4, 5])); // Output: [1, 2, 3, 4, 5]

Efficienza

4. Rilevamento dei Palindromi

Un palindromo è una parola o una frase che si legge allo stesso modo sia da sinistra a destra che da destra a sinistra. La tecnica dei Due Puntatori verifica questo in modo efficiente confrontando i caratteri dalle due estremità.

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) return false; // Mismatch found
    left++;
    right--;
  }

  return true; // It's a palindrome
}

// Example usage:
console.log(isPalindrome("racecar")); // Output: true
console.log(isPalindrome("hello")); // Output: false

Efficienza

5. Rilevamento di Cicli nelle Liste Collegate

Quando si lavora con le liste collegate, un problema comune è rilevare se la lista contiene un ciclo. La tecnica del puntatore lento e veloce (nota anche come Algoritmo di rilevamento dei cicli di Floyd) ci aiuta a farlo in modo efficiente.

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next; // Move 1 step
    fast = fast.next.next; // Move 2 steps

    if (slow === fast) return true; // Cycle detected
  }

  return false; // No cycle found
}

// Example usage:
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
node3.next = node1; // Creating a cycle

console.log(hasCycle(node1)); // Output: true

Efficienza