X'inhi t-teknika taż-żewg-pointer?

Question

Accepted Answer

It-teknika **taż-żewg-pointer** tuża żewg indiċi li jitmekkaw minn sekwenza biex isolvu problemi f'pass wieħed — ittrabat ħafna soluzzjonijiet brute-force O(n²) fi **O(n)**.

## L-idea

Iżżomm żewg pointers (ħafna drabi fit-tripli, jew wieħed bil-mod bil-mod u wieħed malajr) u muévihom abbażi ta' kondizzjoni, nqas ix-xogħol mingħajr re-scan.

## Eżempju: sibt par li jisomma għat-target f'array magħlul

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

## Kumplissità

- **Ħin:** O(n). **Spazju:** O(1).

## Metaħ tuża / trappoli

Grandinuż għal **arrays magħlulin**, ċekk palindrome, inversion, u tneħħija ta' duplikati fil-post. L-array ħafna drabi jkun jrid magħlul għall-varjanti ta' pointer konvergenti. Ħu kura mill-limiti tal-pointer u l-kundizzjoni tal-loop (`lo < hi`).

## Għaliex din hija importanti

Iż-żewg-pointer huwa wieħed mill-aktar pattern ta' intervista ta' leverage għoli: huwa jqabbel loops nested f'scan lineari ħonoż.

It-tgħallmek biex tikseb vantaġġ mill-istruttura (bħal magħlulija) minflok brute force.

L-istess idea tippawer l-merger, il-partizzjonament, u l-pass tal-merge tal-merge sort.