બે-પોઇન્ટર તકનીક શું છે?

Question

Accepted Answer

**બે-પોઇન્ટર** તકનીક એક સમયમાં સમસ્યાઓ હલ કરવા માટે અનુક્રમમાંથી બે ઇન્ડેક્સનો ઉપયોગ કરે છે — ઘણા O(n²) બ્રુટ-ફોર્સ ઉકેલોને **O(n)**માં પરિણત કરે છે।

## વિચાર

બે પોઇન્ટર્સ રાખો (ઘણીવાર છેડે, અથવા એક ધીમો અને એક ઝડપી) અને તેમને શર્તના આધારે ખસેડો, કામ ને સંકુચિત કર્યા વિના પુનરાવર્તન.

## ઉદાહરણ: ક્રમાંકિત શ્રેણીમાં લક્ષ્યનો સરવાળો કરવા માટે જોડી

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

## જટિલતા

- **સમય:** O(n). **અવકાશ:** O(1).

## ક્યારે વાપરો / સમસ્યાઓ

**ક્રમાંકિત શ્રેણી**, પેલિન્ડ્રોમ ચેક, વિરુદ્ધ અને જગ્યામાં ડુપ્લિકેટ્સ દૂર કરવા માટે શ્રેષ્ઠ. સમીપ પોઇન્ટર વેરિયન્ટ માટે શ્રેણી ઘણીવાર ક્રમાંકિત હોવી જોઈએ. પોઇન્ટર બાઉન્ડ્સ અને લૂપ શર્ત (`lo < hi`) ની સાવચેતીથી કામ લો.

## તેનું મહત્ત્વ શા માટે છે

બે-પોઇન્ટર સૌથી વધુ મહત્વપૂર્ણ ઇન્ટરવ્યુ પેટર્નમાંથી એક છે: તે નેસ્ટેડ લૂપ્સને સ્વચ્છ રેખીય સ્કેનમાં ઘટાડે છે.

તમને બ્રુટ ફોર્સના બદલે માળખું (જેમ કે સોર્ટનેસ) નો ફાયદો લેવાનું શીખવે છે.

યही વિચાર મર્જ, પાર્ટીશનિંગ અને મર્જ સોર્ટના મર્જ પગલાને શક્તિ આપે છે.