Che cos'è la tecnica dei due puntatori?

Question

IT Interview Practice · Accepted Answer

La tecnica **two-pointer** utilizza due indici che si muovono attraverso una sequenza per risolvere problemi in un'unica passata — trasformando molte soluzioni di brute-force O(n²) in **O(n)**.

## L'idea

Mantenere due puntatori (spesso agli estremi, oppure uno lento e uno veloce) e muoverli in base a una condizione, riducendo il lavoro senza riscansionare.

## Esempio: trovare una coppia che somma a un valore target in un array ordinato

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Complessità

- **Tempo:** O(n). **Spazio:** O(1).

## Quando usarla / insidie

Ottima per **array ordinati**, controlli di palindromi, inversioni e rimozione di duplicati in place. L'array deve essere generalmente ordinato per la variante con puntatori convergenti. Stai attento ai limiti dei puntatori e alla condizione del ciclo (`lo < hi`).

## Perché è importante

Due puntatori è uno dei pattern di intervista con il massimo valore: collassa i cicli annidati in una scansione lineare pulita.

Ti insegna a sfruttare la struttura (come l'ordinamento) invece di usare la forza bruta.

La stessa idea alimenta il merge, il partizionamento e il passo di merge del merge sort.

L'idea

Esempio: trovare una coppia che somma a un valore target in un array ordinato

Complessità

Quando usarla / insidie

Perché è importante

Domande correlate