Two Pointers - படிப்படையாக புரிந்துகொள்வோம்

Two Pointers என்றால் என்ன?

Two pointers என்பது:

ஒரு array-இல் இரண்டு index-களை பயன்படுத்தும் ஒரு முறையாகும்.

பொதுவாக:

• left (இடது பக்கம்)
• right (வலது பக்கம்)

இந்த இரண்டு pointers-ஐ condition அடிப்படையில் நகர்த்தி பிரச்சினையை தீர்க்கிறோம்.

---

ஏன் Two Pointers பயன்படுத்த வேண்டும்?

ஒரு சாதாரண பிரச்சினை:

“இரண்டு numbers-ன் sum = target ஆக வருகிறதா?”

சாதாரண (brute force) முறை

for i in range(n):
    for j in range(i + 1, n):
        if arr[i] + arr[j] == target:
            print(i, j)

Time complexity: O(n²)

இது பெரிய data-க்கு slow ஆகும்.

Efficient approach (two pointers)

Array sorted ஆக இருந்தால்:

arr = [1, 2, 3, 4, 5]
target = 6

நாம் O(n) நேரத்தில் தீர்க்கலாம்.

---

Pattern 1: Pair sum - pair_sum

def pair_sum(arr, target):
    left = 0
    right = len(arr) - 1

    while left < right:
        s = arr[left] + arr[right]

        if s == target:
            return True

        elif s < target:
            left += 1

        else:
            right -= 1

    return False

செயல்முறை (step-by-step)

• left = 0 → value 1
• right = 4 → value 5
• sum = 1 + 5 = 6 → target → கிடைத்தது

முக்கியமான logic

நிலை	நடவடிக்கை
Sum சிறியதா இலக்கு	left pointer முன்னேறு
Sum பெரியதா இலக்கு	right pointer பின்செல்
Sum சமம் இலக்கு	விடை கிடைத்தது

---

இது எப்படி வேலை செய்கிறது?

Array sorted ஆக இருப்பதால்:

• left pointer நகர்த்தினால் sum பொதுவாக அதிகரிக்கும் (சிறிய மதிப்புகளிலிருந்து பெரிய பக்கம்).
• right pointer நகர்த்தினால் sum குறையும்.

---

Pattern 2: Pair counting - pair_counting

“எத்தனை pairs sum ≤ target?”

def count_pairs(arr, target):
    left = 0
    right = len(arr) - 1
    count = 0

    while left < right:
        if arr[left] + arr[right] <= target:
            count += (right - left)
            left += 1
        else:
            right -= 1

    return count

ஏன் count += (right - left)?

ஒரு pair valid என்றால், இந்த pattern-இல் இந்த arr[left] உடன் left + 1 முதல் right வரையிலான சில pair-க்கள் ஏற்கத்தக்கது போல் தொகுக்கும் (monotone அமைப்பின் அடிப்படையில்).

(Duplicates மற்றும் exact problem statement-ன் அடிப்படையில் எல்லாவற்றையும் மீண்டும் சரிபார்ப்பது முக்கியம்.)

---

Pattern 3: Pointer movement strategy - pair_selection_strategy

Two pointers-இல் மிக முக்கியமான skill:

“எந்த pointer-ஐ நகர்த்த வேண்டும்?”

நீங்கள் கேட்க வேண்டியது:

• Sum சிறியதா? → left முன்செல்லுதல்
• Sum பெரியதா? → right பின்செல்லுதல்

---

Pattern 4: Incremental Pair Update - incremental_pair_update

சில பிரச்சினைகளில் array values update ஆகும் போது, pair-based result-ஐ முழுவதும் மீண்டும் கணக்கிடாமல் புதுப்பிக்க வேண்டும்.

எளிய உதாரணம்: adjacent pairs-இல் even-sum pair count-ஐ maintain செய்வது.

arr = [1, 3, 2, 4]

def is_even_pair(a, b):
    return (a + b) % 2 == 0

count = sum(1 for i in range(len(arr) - 1) if is_even_pair(arr[i], arr[i + 1]))

idx என்ற index value மட்டும் மாறினால், change ஆகக்கூடியவை அருகிலுள்ள pairs மட்டும்:

• (idx - 1, idx)
• (idx, idx + 1)

அதனால்:

1. மாறும் pair-களின் பழைய contribution-ஐ கழி
2. value update செய்
3. புதிய contribution-ஐ சேர்த்து count-ஐ புதுப்பு

இதே தான் incremental pair update-ன் முக்கிய யோசனை.

---

Pattern 5: Order Preservation - order_preservation

சில two-pointer பிரச்சினைகளில் valid elements-ன் original relative order காக்கப்பட வேண்டும்.

உதாரணம்: zeros-ஐ end-க்கு நகர்த்தும் போது, non-zero elements order மாறக்கூடாது.

def move_zeros_stable(nums):
    write = 0

    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

nums = [0, 1, 0, 3, 12] என்றால் output [1, 3, 12, 0, 0]. இங்கு 1, 3, 12 வந்த வரிசை அதேபடி காக்கப்படுகிறது.

---

Pattern 6: Partitioning - partitioning

Partitioning என்பது array-ஐ சில பகுதிகளாக பிரிப்பது (சாதாரணமாக pivot சுற்றி).

def partition(arr, pivot):
    left = 0

    for right in range(len(arr)):
        if arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1

உதாரணம்

arr = [5, 2, 8, 1, 3]
pivot = 4

முடிவு:

[2, 1, 3, 5, 8]

---

Pattern 7: Partition optimization - partition_optimization

சில நேரங்களில் array-ஐ 3 பகுதிகளாக பிரிக்க வேண்டும்:

1. pivot-க்குக் குறைந்தவை
2. pivot-க்கு சமமானவை
3. pivot-க்கு அதிகமானவை

இதற்கு 3-way partitioning பயன்படுத்தப்படுகிறது (duplicates அதிகமாக இருக்கும் போது பயனுள்ளது).

---

Time complexity

Pattern	Time
Pair sum	O(n)
Pair counting	O(n)
Partition	O(n)

---

எப்போது two pointers பயன்படுத்தலாம்?

• Array sorted ஆக இருக்கும் போது (pair meet-in-middle style)
• Pair / combination பிரச்சினைகள்
• O(n²) → O(n) optimization தேவை
• Partitioning பிரச்சினைகள்

---

பொதுவான பிழைகள்

• Unsorted array-இல் நிபந்தனை இல்லாமல் பயன்படுத்துவது
• Pointer update தவறு
• Condition சரியாக எழுதாதது
• Duplicate pairs தவறாக count செய்வது

---

பயிற்சி

• Pair sum கண்டுபிடிக்க
• Pair count ≤ target
• Array-இல் zeros-ஐ end-க்கு நகர்த்த
• Pivot அடிப்படையில் partition செய்ய

---

முக்கிய புரிதல்

Two pointers என்பது:

• ஒரு technique மட்டும் அல்ல
• ஒரு problem-solving mindset

---

இறுதி கருத்து

நீங்கள் பார்க்கும் போது:

• Pair பிரச்சினைகள்
• Sorted arrays
• Optimization தேவை

உடனே நினைக்க வேண்டும்:

“Two pointers பயன்படுத்த முடியுமா?”

Continue here:

/resources/arrays/advanced