دو پوائنٹر تکنیک کیا ہے؟

Question

Accepted Answer

**دو پوائنٹر** تکنیک دو انڈیکسز استعمال کرتی ہے جو ایک ترتیب میں حرکت کرتے ہوئے مسائل کو ایک پاس میں حل کرتے ہیں — بہت سے O(n²) brute-force حل کو **O(n)** میں تبدیل کرتے ہوئے۔

## نظریہ

دو pointers رکھیں (اکثر سرے پر، یا ایک سست اور ایک تیز) اور انہیں ایک شرط کی بنیاد پر حرکت دیں، کام کو کم کریں بغیر دوبارہ سکیننگ کے۔

## مثال: ایک ترتیب شدہ 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
```

## پیچیدگی

- **وقت:** O(n)۔ **جگہ:** O(1)۔

## کب استعمال کریں / نقصانات

**ترتیب شدہ arrays** کے لیے بہترین، palindrome کی جانچ، الٹا کرنا، اور duplicates کو جگہ میں ہٹانا۔ converging-pointer variant کے لیے array اکثر ترتیب شدہ ہونا ضروری ہے۔ pointer bounds اور loop condition (`lo < hi`) کے ساتھ احتیاط کریں۔

## اہمیت

دو pointers انٹرویو کے سب سے زیادہ اثر والے نمونوں میں سے ایک ہے: یہ nested loops کو ایک صاف linear scan میں گھما دیتا ہے۔

یہ آپ کو structure (جیسے sortedness) کو استعمال کرنا سکھاتا ہے brute force کی بجائے۔

یہی نظریہ merging، partitioning، اور merge sort کے merge step کو طاقت دیتا ہے۔