Due puntatori: lento e veloce

Lo schema slow-fast (chiamato anche schema della tartaruga e della lepre) usa due puntatori che si muovono a velocità diverse nella stessa sequenza. A differenza dei puntatori alle estremità opposte, entrambi partono dall'inizio. Il puntatore slow avanza di un passo alla volta, mentre il puntatore fast ne percorre due (o più). La differenza di velocità crea invarianti utili: slow tiene traccia di un prefisso valido, mentre fast scansiona in avanti alla ricerca di condizioni.

In un array ordinato, i duplicati sono adiacenti. Il puntatore slow tiene traccia dell'ultimo valore unico scritto, mentre fast scansiona in avanti. Ogni volta che fast raggiunge un valore diverso da nums[slow], faccia avanzare slow e copi il nuovo valore. Questo algoritmo in-place richiede tempo O(n) e spazio aggiuntivo O(1): è una domanda tipica dei colloqui tecnici, che verifica la padronanza del modello del puntatore di lettura-scrittura.

Sposti tutti gli zeri alla fine mantenendo l'ordine relativo degli elementi diversi da zero. Il puntatore slow indica la posizione successiva destinata a un elemento diverso da zero. Il puntatore fast scansiona alla ricerca di valori diversi da zero. Quando fast ne trova uno, lo copi nella posizione di slow e faccia avanzare entrambi. Al termine della scansione, riempia di zeri le posizioni da slow alla fine. Tempo O(n), spazio O(1).

La fase di partizionamento di quicksort riorganizza gli elementi in-place in modo che tutti i valori < pivot precedano i valori >= pivot. Lo schema di Lomuto usa un puntatore slow, che indica l'ultima posizione di un elemento piccolo, e un puntatore fast, che scansiona in avanti. Quando fast trova un elemento piccolo, incrementi slow ed esegua uno scambio. Questo richiede tempo O(n) e spazio aggiuntivo O(1).

Con i puntatori slow-fast su una lista concatenata, il puntatore fast avanza di due nodi per passo, mentre slow avanza di uno. Quando fast raggiunge la fine, slow si trova al centro. Questo approccio in un'unica scansione, in O(n), è molto più semplice che contare i nodi e poi percorrere metà della lista. Viene usato come fase intermedia nel merge sort per liste concatenate e nel rilevamento di palindromi in liste concatenate.

Il rilevamento dei cicli di Floyd colloca i puntatori slow e fast all'inizio di una lista concatenata. Slow avanza di un nodo, mentre fast ne avanza due. Se esiste un ciclo, il puntatore fast raggiungerà prima o poi slow e i due si incontreranno all'interno del ciclo. Se fast raggiunge None, il ciclo non esiste. L'incontro è garantito perché fast guadagna un passo su slow a ogni iterazione: in un ciclo di lunghezza k, i due si incontrano entro k passi dall'ingresso di slow nel ciclo.

Dopo aver rilevato un ciclo (slow == fast), reimposti uno dei puntatori su head. A questo punto faccia avanzare entrambi i puntatori di un passo alla volta. Si incontreranno nel punto di ingresso del ciclo. Questo sfrutta la proprietà matematica secondo cui la distanza da head all'ingresso del ciclo è uguale alla distanza dal punto d'incontro all'ingresso del ciclo (modulo la lunghezza del ciclo). È un elegante risultato matematico che compare spesso nei problemi difficili dei colloqui tecnici.

I puntatori slow-fast si applicano, oltre che alle liste concatenate, a qualsiasi processo che presenti cicli. Un «numero felice» attraversa una sequenza di somme dei quadrati delle cifre: se n non è felice, la sequenza finisce per ripetersi in un ciclo. Rilevi il ciclo con slow (un passo = una somma dei quadrati delle cifre) e fast (due passi). Se si incontrano in 1, n è felice; altrimenti è intrappolato in un ciclo che non contiene 1. Si tratta dell'algoritmo di Floyd applicato a una lista concatenata virtuale di valori.

Trovi l'n-esimo nodo dalla fine di una lista concatenata in un'unica scansione usando due puntatori. Faccia avanzare il puntatore fast di n passi. Poi faccia avanzare entrambi i puntatori insieme finché fast raggiunge la fine: slow si trova ora sull'n-esimo nodo dalla fine. Per eliminare questo nodo, mantenga un puntatore 'prev' un passo indietro rispetto a slow. È un classico problema sulle liste concatenate in un'unica scansione, che evita di dover contare prima la lunghezza totale.

Il ragionamento slow-fast si applica anche ai problemi su array e stringhe. Quando comprime una stringa con codifica run-length, il puntatore slow indica la posizione di scrittura e fast scansiona fino alla fine di ogni sequenza. Quando tutti i caratteri della sequenza sono uguali al carattere di slow, faccia avanzare fast; altrimenti registri la sequenza e aggiorni slow. Si ottiene O(n) in un'unica scansione con spazio O(1).

Usi i puntatori alle estremità opposte quando il problema riguarda coppie la cui somma è uguale a un valore target, la verifica di palindromi o la riduzione di una finestra da entrambi i lati. Usi i puntatori slow-fast quando serve un puntatore di scrittura (per rimuovere o spostare elementi), quando si lavora sulla struttura di una lista concatenata (nodo centrale, ciclo) o quando si rilevano cicli in una sequenza di valori qualsiasi. Entrambi eliminano i cicli annidati e raggiungono O(n): il fattore decisivo è la struttura dell'attraversamento.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha appreso che: il modello slow-fast (lettura-scrittura) mantiene un puntatore di scrittura sulla posizione valida successiva mentre un puntatore fast scansiona in avanti: è la base della rimozione in-place, della deduplicazione e dello spostamento degli zeri, il metodo della tartaruga e della lepre di Floyd rileva i cicli in tempo O(n) e spazio O(1) sfruttando la differenza di velocità tra due puntatori e dopo aver rilevato un ciclo, reimpostare un puntatore su head e far avanzare entrambi alla stessa velocità permette di trovare l'ingresso del ciclo grazie a una dimostrabile uguaglianza delle distanze. Ora esamineremo l'API delle stringhe Python per i colloqui tecnici.