Apa itu teknik dua-pointer?

Question

Accepted Answer

Teknik **dua-pointer** menggunakan dua indeks yang bergerak melalui urutan untuk menyelesaikan masalah dalam satu lintasan — mengubah banyak solusi brute-force O(n²) menjadi **O(n)**.

## Idenya

Pertahankan dua pointer (sering di ujung, atau satu lambat dan satu cepat) dan pindahkan berdasarkan kondisi, mengurangi pekerjaan tanpa pemindaian ulang.

## Contoh: menemukan pasangan yang berjumlah ke target dalam array yang diurutkan

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

## Kompleksitas

- **Waktu:** O(n). **Ruang:** O(1).

## Kapan digunakan / jebakan

Sangat cocok untuk **array yang diurutkan**, pemeriksaan palindrom, pembalikan, dan menghapus duplikat di tempat. Array sering kali harus diurutkan untuk varian pointer konvergen. Hati-hati dengan batas pointer dan kondisi loop (`lo < hi`).

## Mengapa ini penting

Dua-pointer adalah salah satu pola wawancara dengan leverage tertinggi: mengubah loop bersarang menjadi pemindaian linier yang bersih.

Ini mengajarkan Anda untuk memanfaatkan struktur (seperti ketertarsuran) daripada brute force.

Ide yang sama mendukung penggabungan, partisi, dan langkah penggabungan dari merge sort.