दो-पॉइंटर तकनीक क्या है?

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`) के साथ सावधान रहें।

## यह महत्वपूर्ण क्यों है

दो-पॉइंटर सबसे अधिक प्रभावशाली साक्षात्कार पैटर्न में से एक है: यह नेस्टेड लूप्स को एक स्वच्छ रैखिक स्कैन में संक्षिप्त करता है।

यह आपको ब्रूट फोर्स के बजाय संरचना (जैसे क्रमबद्धता) का दोहन करना सिखाता है।

यही विचार मर्जिंग, विभाजन, और मर्ज सॉर्ट के मर्ज चरण को शक्ति देता है।