Two Pointers और Sliding Window
Smart Scanning क्यों ज़रूरी है
सोचिए कि एक AI किसी live video feed पर संदिग्ध गतिविधि monitor कर रहा है। वो हर सेकंड पूरी recording दोबारा नहीं देख सकता - उसे stream पर एक attention की window slide करनी होती है, बस उतना context रखते हुए जितना ज़रूरी है। Two pointers और sliding window patterns sequential data के साथ बिल्कुल यही करते हैं।
दोनों techniques brute-force O(n²) scans को elegant O(n) passes में बदल देती हैं।
Two Pointer Technique
किसी sequence में दो references रखो और उन्हें एक rule के हिसाब से move करो। इसके दो मुख्य तरीके हैं।
Converging Pointers
एक pointer शुरू में और एक अंत में रखो, फिर अंदर की तरफ़ move करो। Sorted data के लिए बेहतरीन है।
Classic problem - Pair Sum: एक sorted array दिया है, दो numbers ढूँढो जिनका sum target के बराबर हो।
function pairSum(arr, target):
left = 0
right = arr.length - 1
while left < right:
sum = arr[left] + arr[right]
if sum == target: return (left, right)
if sum < target: left += 1
else: right -= 1
return null
क्योंकि array sorted है, left को right move करने से sum बढ़ता है, और right को left move करने से sum घटता है - इससे कोई भी valid pair miss नहीं होती।
Same-Direction Pointers
दोनों pointers आगे की तरफ़ move करते हैं, लेकिन अलग-अलग speed से। Partitioning या cycle detection के लिए useful है।
Example - Duplicates in-place remove करो: एक slow pointer write position mark करता है; एक fast pointer आगे scan करता है।
function removeDuplicates(arr):
slow = 0
for fast in 1..arr.length - 1:
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1
Converging two-pointer technique में sorted array पर, जब current sum target से कम हो तो क्या करना चाहिए?
Discussion
Sign in to join the discussion