দুই-পয়েন্টার কৌশল কী?

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`) এ সতর্ক থাকুন।

## কেন গুরুত্বপূর্ণ

দুই পয়েন্টার সর্বোচ্চ-লাভজনক সাক্ষাৎকার প্যাটার্নগুলির মধ্যে একটি: এটি নেস্টেড লুপগুলিকে একটি পরিষ্কার রৈখিক স্ক্যানে সংকুচিত করে।

এটি আপনাকে শক্তিশালী শক্তির পরিবর্তে কাঠামো (যেমন সর্টনেস) কাজে লাগাতে শেখায়।

এই একই ধারণা বিলয়, পার্টিশনিং এবং মার্জ সর্টের মার্জ ধাপকে শক্তি দেয়।