# Two Pointers — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/two-pointers

> अनुक्रम में चलते दो इंडेक्स जो nested loop को एकल पास से बदल देते हैं।

## अभिसरण या पीछा

**विपरीत सिरे**: `left` और `right` एक-दूसरे की ओर (sorted two-sum, palindrome, container with most water)। **एक ही दिशा**: धीमा और तेज़ पॉइंटर (जगह पर duplicate हटाना, cycle पहचान)। `O(n^2)` को `O(n)` बनाता है।

## Sorted two-sum

यदि योग बहुत छोटा है, केवल `left` ऊपर करना मदद करेगा; बहुत बड़ा तो केवल `right` नीचे।

```python
def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []
```

**Quiz:** विपरीत-सिरे two-pointer तरकीब को array चाहिए...

- [x] Sorted
- [ ] सभी धनात्मक
- [ ] सम लंबाई

*Answer:* Sorted. Sorted क्रम ही तय करने देता है कि वर्तमान योग से कौन-सा पॉइंटर हिलाना है।