ਦੋ-ਪੁਆਇੰਟਰ ਤਕਨੀਕ ਕੀ ਹੈ?

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`)।

## ਇਹ ਮਾਯਨੇ ਕਿਉਂ ਰੱਖਦਾ ਹੈ

ਦੋ-ਪੁਆਇੰਟਰ ਸਭ ਤੋਂ ਉੱਚ-ਲਾਭਕਾਰੀ ਇੰਟਰਵਿਊ ਪ੍ਰੋ pattern ਵਿੱਚੋਂ ਇੱਕ ਹੈ: ਇਹ ਨਸਲਬੰਦ ਲੂਪਸ ਨੂੰ ਸਾਫ ਰੇਖਾ ਸਕੈਨ ਵਿੱਚ ਤਬਦੀਲ ਕਰਦਾ ਹੈ।

ਇਹ ਤੁਹਾਨੂੰ ਜ਼ੋਰ-ਜ਼ਬਰਦਸਤੀ ਦੀ ਜਗ੍ਹਾ ਢਾਂਚੇ (ਜਿਵੇਂ ਸਾਜਿਸ਼) ਦਾ ਫਾਇਦਾ ਉਠਾਉਣ ਦੀ ਮੇਨੂ ਕਰਦਾ ਹੈ।

ਇਹੀ ਵਿਚਾਰ ਮਰਜਿੰਗ, ਪਾਰਟੀਸਨਿੰਗ ਅਤੇ ਮਰਜ ਸਾਰਟ ਦੇ ਮਰਜ ਪੜਾਵ ਨੂੰ ਸ਼ਕਤੀ ਦਿੰਦਾ ਹੈ।