दोन-पॉइंटर तंत्र म्हणजे काय?

Question

Accepted Answer

**दोन-पॉइंटर** तंत्र क्रमाच्या माध्यमातून हलणारे दोन निर्देशांक वापरून एका पासामध्ये समस्या सोडवते — अनेक O(n²) brute-force उपायांना **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).

## कधी वापरायचे / नुकसान

**क्रमबद्ध arrays**, palindrome तपास, उलट करणे, आणि डुप्लिकेट्स जागी काढणे यासाठी उत्तम. Converging-pointer variant साठी array सामान्यत: क्रमबद्ध असणे आवश्यक आहे. पॉइंटर सीमा आणि लूप स्थितीसाठी (`lo < hi`) सावधान रहा.

## हे महत्वाचे का आहे

दोन-पॉइंटर हे सर्वोच्च-लीव्हरेज मुलाखत नमुन्यांपैकी एक आहे: हे nested loops ला स्वच्छ रेषीय स्कॅनमध्ये बदलते.

हे तुम्हाला brute force च्या बजाय संरचना (जसे sortedness) चा फायदा घेऊन काम करायला शिकवते.

हीच कल्पना merging, partitioning, आणि merge sort च्या merge step ला शक्ती देते.