Apa iku teknik rong-pointer?

Question

Accepted Answer

Teknik **rong-pointer** nggunakake rong indeks sing obah-obahan ing urutan kanggo ngatasi masalah ing siji pass — ngowah akeh solusi brute-force O(n²) dadi **O(n)**.

## Ideane

Jaga rong pointer (asring ing sisine, utawa siji alon lan siji cepet) lan gerakake adhedhasar kondisi, ngecilake kerja tanpa nrescan.

## Conto: golek sepasang sing jumlahne target ing array sing diurut

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

## Kerumitan

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

## Kapan digunakake / benciwir

Sangat apik kanggo **array sing diurut**, cek palindrom, balik, lan ngilangi duplikat ing papan. Array asring kudu diurut kanggo varian pointer converging. Ati-ati karo wates pointer lan kondisi loop (`lo < hi`).

## Mengapa iku penting

Rong pointer minangka salah siji pola intervyu paling dhuwur-leverage: nyisir loop nested dadi scan linear sing resik.

Dheweke ngajari sampeyan kanggo ngmanfaatke struktur (kaya urutan) tinimbang brute force.

Ideane padha nyalangi merging, partisioning, lan langkah merge saka merge sort.