Wat is de two-pointer-techniek?

Question

IT Interview Practice · Accepted Answer

De **two-pointer**-techniek gebruikt twee indices die door een reeks bewegen om problemen in één pass op te lossen — veel O(n²) brute-force-oplossingen worden omgezet naar **O(n)**.

## Het idee

Behoud twee pointers (vaak aan de uiteinden, of één langzaam en één snel) en verplaats ze op basis van een voorwaarde, waardoor het werk inkrimpt zonder opnieuw te scannen.

## Voorbeeld: getallenparen die optellen tot een doel in een gesorteerde array

```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
```

## Complexiteit

- **Tijd:** O(n). **Ruimte:** O(1).

## Wanneer te gebruiken / valkuilen

Geweldig voor **gesorteerde arrays**, palindroomcontroles, omkering en het ter plaatse verwijderen van duplicaten. De array moet vaak worden gesorteerd voor de convergerende-pointer-variant. Wees voorzichtig met pointerlimieten en de lusvoorwaarde (`lo < hi`).

## Waarom het belangrijk is

Two-pointer is één van de meest krachtige interviewpatronen: het vouwt geneste lussen in een schone lineaire scan.

Het leert je om structuur (zoals gesorteerd zijn) uit te buiten in plaats van brute force.

Dezelfde idee ondersteunt het samenvoegen, partitioneren en de samenvoegstap van merge sort.

Het idee

Voorbeeld: getallenparen die optellen tot een doel in een gesorteerde array

Complexiteit

Wanneer te gebruiken / valkuilen

Waarom het belangrijk is

Gerelateerde vragen