రెండు-పాయింటర్ టెక్నిక్ అంటే ఏమిటి?

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).

## ఎప్పుడు ఉపయోగించాలి / ఆపత్తులు

**క్రమబద్ధమైన శ్రేణులకు**, పాలిండ్రోమ్ చెక్‌ల కోసం, రివర్సింగ్, మరియు నకలులను స్థానంలో తీసివేయడానికి గ్రేట్. శ్రేణి తరచుగా కలయిక-పాయింటర్ రూపాంతరణ కోసం క్రమబద్ధీకరించబడాలి. పాయింటర్ సీమలు మరియు లూప్ పరిస్థితి (`lo < hi`) గురించి జాగ్రత్తగా ఉండండి.

## ఇది ఎందుకు ముఖ్యమైనది

రెండు-పాయింటర్ అత్యధిక-లిভరేజ్ ఇంటర్వ్యూ నమూనాలలో ఒకటి: ఇది నెస్టెడ్ లూప్‌లను స్వచ్ఛమైన సరళ స్కాన్‌గా కూలిపోయిస్తుంది.

ఇది brute force కు బదులుగా నిర్మాణాన్ని ఉపయోగించుకోవడం నేర్పిస్తుంది.

ఇదే ఆలోచన విలీనం, విభజన, మరియు merge sort యొక్క విలీనం దశను శక్తిచేస్తుంది.