AI & ఇంజనీరింగ్ ప్రోగ్రామ్‌లు›🪨 AI Chisel›పాఠాలు›Two Pointers మరియు Sliding Window

👆

AI Chisel • మధ్యస్థం⏱️ 15 నిమిషాల పఠన సమయం

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 గా మారుస్తాయి.

Array రెండు చివరల నుండి converge అవుతున్న two pointers మరియు data stream మీద కదులుతున్న sliding window — Two pointers search space ను తగ్గిస్తాయి; sliding window ఒక running view ను maintain చేస్తుంది.

Two Pointer Technique

ఒక sequence లో రెండు references ఉంచి, ఒక rule ప్రకారం వాటిని move చేయండి. రెండు ప్రధాన రకాలు ఉన్నాయి.

Converging Pointers

ఒక pointer ప్రారంభంలో, మరొకటి చివరలో ఉంచి, లోపలికి move చేయండి. Sorted data కు అద్భుతం.

Classic problem - Pair Sum: ఒక sorted array ఇస్తే, target కు add అయ్యే రెండు numbers కనుగొనండి.

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 అవుతాయి, కానీ వేర్వేరు speeds తో. 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

🧠త్వరిత తనిఖీ

Sorted array మీద converging two-pointer technique లో, current sum target కంటే తక్కువగా ఉన్నప్పుడు ఏమి చేయాలి?

పాఠం 1 / 100% పూర్తి

←ప్రోగ్రామ్‌కు తిరిగి

Discussion

lessons.suggestEdit

Sliding Window Pattern

Sliding window ఒక contiguous sub-sequence ను maintain చేస్తుంది, దాని size k (fixed) లేదా variable, మరియు aggregates ను scratch నుండి recalculate చేయకుండా incrementally update చేస్తుంది.

సరిగ్గా k elements ఉన్న window ను array మీద slide చేయండి.

Example - ఏదైనా k consecutive elements యొక్క maximum sum:

function maxSubarraySum(arr, k):
    windowSum = sum(arr[0..k-1])
    best = windowSum
    for i in k..arr.length - 1:
        windowSum += arr[i] - arr[i - k]
        best = max(best, windowSum)
    return best

ప్రతి step లో window లోకి వచ్చే కొత్త element add అవుతుంది, బయటికి వెళ్ళేది subtract అవుతుంది - O(1) per move.

Variable-Size Window

మరింత data include చేయడానికి window ను expand చేయండి, constraint violate అయినప్పుడు shrink చేయండి.

Example - Repeating characters లేని longest substring:

function longestUnique(s):
    seen = {}
    left = 0
    best = 0
    for right in 0..s.length - 1:
        if s[right] in seen and seen[s[right]] >= left:
            left = seen[s[right]] + 1
        seen[s[right]] = right
        best = max(best, right - left + 1)
    return best

🤯

Apache Flink వంటి streaming analytics platforms sliding మరియు tumbling windows ను first-class primitives గా ఉపయోగిస్తాయి - ఇదే concept సెకనుకు millions of events కు scale అవుతుంది.

Real AI Applications

| Pattern | AI Use Case | |---------|------------| | Fixed window | చివరి k sensor readings మీద anomaly detection | | Variable window | అన్ని query keywords ఉన్న అతి చిన్న text span కనుగొనడం (search engines) | | Converging pointers | Sorted embedding dimensions లో efficient nearest-neighbour checks | | Same-direction pointers | Multiple retrieval models నుండి sorted result lists ను merge చేయడం |

🤔

Think about it:ఒక voice assistant wake word detect చేయడానికి చివరి 3 seconds audio ను buffer చేస్తుంది. ఇది ఏ pattern - fixed window లేదా variable window? Wake word buffer కంటే పెద్దదైతే ఏమి జరుగుతుంది?

ఏ Pattern ఎప్పుడు వాడాలి

Two pointers (converging): sorted input, pair/triplet search, palindrome checks.
Two pointers (same-direction): in-place modifications, fast/slow runner problems.
Fixed sliding window: తెలిసిన window size మీద aggregate.
Variable sliding window: ఒక condition ను satisfy చేసే అతి చిన్న లేదా అతి పెద్ద window కనుగొనడం.

🧠త్వరిత తనిఖీ

ఇచ్చిన value కంటే ఎక్కువ sum ఉన్న అతి చిన్న subarray కనుగొనడానికి ఏ pattern ఎంచుకుంటారు?

🤔

Think about it:Two pointers ను sliding window తో combine చేయగలరా? Rolling data window లో pair కనుగొనాల్సిన problems గురించి ఆలోచించండి - ఉదాహరణకు, ఐదు నిమిషాల window లో duplicate transactions detect చేయడం.

Two pointers ordering లేదా partitioning ను ఉపయోగించి nested loops ను eliminate చేస్తాయి.
Sliding windows running state maintain చేస్తాయి, తద్వారా ప్రతి element గరిష్ఠంగా రెండుసార్లు process అవుతుంది.
రెండు patterns real-time AI pipelines లో foundational - anomaly detection నుండి search ranking వరకు.

🧠త్వరిత తనిఖీ

Brute-force nested loop ను two-pointer లేదా sliding-window solution గా మార్చినప్పుడు సాధారణంగా ఏ time complexity వస్తుంది?

AI పునాదులు

AI నైపుణ్యం

కెరీర్ రెడీ

ల్యాబ్

Two Pointers మరియు Sliding Window

Smart Scanning ఎందుకు ముఖ్యం

Two Pointer Technique

Converging Pointers

Same-Direction Pointers

Discussion

Sliding Window Pattern

Fixed-Size Window

Variable-Size Window

Real AI Applications

ఏ Pattern ఎప్పుడు వాడాలి

Key Takeaways