Two Pointers

Intuition

Watch the bars below: one pointer starts at each end and steps inward — too small, move left up; too big, move right down — until they meet or find a pair that sums to the target.

Tushuncha (Intuition)

Quyidagi ustunlarga qarang: bitta pointer har uchdan boshlanadi va ichkariga qadam tashlaydi — yig'indi kichik bo'lsa, left'ni oldinga suring; katta bo'lsa, right'ni orqaga torting — toki ular uchrashguncha yoki yig'indisi target'ga teng juftlik topilguncha.

How It Works

Set two pointers: left = 0 and right = len(arr) - 1, pointing at the two ends of the sorted array.
While left < right, there are still two distinct elements to check, so compute the current pair sum: arr[left] + arr[right].
If the sum equals target, you've found the pair — return the two indices right away.
If the sum is smaller than target, the only move that can raise it is dropping the smallest value still in play — move left += 1. Moving right down would replace a large value with a smaller one and push the sum even further from target.
If the sum is bigger than target, the mirror move applies: drop the largest value still in play by moving right -= 1, and leave left alone.
Go back to step 2 with the narrowed [left, right] range — exactly one pointer has moved one step closer to the other.
Stop when left meets or crosses right: every possible pair has been considered exactly once, and none summed to target, so no answer exists.

Qanday Ishlaydi

Ikkita pointer o'rnating: left = 0 va right = len(arr) - 1 — bular saralangan array'ning ikki uchini ko'rsatadi.
left < right bo'lar ekan, hali tekshirish uchun ikkita alohida element bor, shuning uchun joriy juftlik yig'indisini hisoblang: arr[left] + arr[right].
Agar yig'indi targetga teng bo'lsa — juftlik topildi, darhol ikkala indeksni qaytaring.
Agar yig'indi targetdan kichik bo'lsa, uni oshirishning yagona yo'li — hozircha ishtirokdagi eng kichik qiymatni tashlab yuborish: left += 1 qiling. rightni orqaga surish esa katta qiymatni kichikroqqa almashtirib, yig'indini target'dan yanada uzoqlashtirar edi.
Agar yig'indi targetdan katta bo'lsa, aksincha harakat qiling: hozircha ishtirokdagi eng katta qiymatni tashlab yuborish uchun right -= 1 qiling, leftni esa tinch qoldiring.
Yangi, toraygan [left, right] maydoni bilan 2-qadamga qayting — aynan bitta pointer ikkinchisiga bir qadam yaqinlashdi.
left rightga yetganda yoki undan oshib ketganda to'xtang: har bir mumkin bo'lgan juftlik aynan bir marta ko'rib chiqildi va hech biri targetga teng yig'indi bermadi, demak javob yo'q.

Complexity

Time: O(n). Every iteration moves exactly one pointer one step inward — either left up or right down — and never moves a pointer back outward. Since the gap between left and right starts at n - 1 and shrinks by at least one on every iteration, the loop can run at most n times before the pointers meet. No pair of indices is ever compared twice, so a single pass — not a nested loop over all pairs — is enough to check every candidate that matters.

Space: O(1). The algorithm tracks only two index variables, left and right, no matter how large the array is — it never allocates a second array, hash map, or any structure that grows with the input.

Murakkablik

Vaqt: O(n). Har bir iteratsiya aynan bitta pointer'ni bir qadam ichkariga suradi — yoki leftni oldinga, yoki rightni orqaga — va hech qachon pointer'ni tashqariga qaytarmaydi. left va right orasidagi masofa n - 1dan boshlanib har bir iteratsiyada kamida bittaga qisqargani uchun, loop pointer'lar uchrashguncha ko'pi bilan n marta ishlaydi. Hech qanday indekslar jufti ikki marta solishtirilmaydi, shuning uchun barcha juftliklar ustidan nested loop emas, bitta pass yetarli.

Xotira: O(1). Algoritm array qanchalik katta bo'lishidan qat'i nazar faqat ikkita indeks o'zgaruvchisini — left va rightni — kuzatib boradi; u hech qachon ikkinchi array, hash map yoki kirish hajmiga qarab o'sadigan boshqa struktura yaratmaydi.

Common Mistakes

Moving the wrong pointer when the sum misses the target — e.g. pulling right down when the sum is too small. Fix: reason from the sorted order — a too-small sum can only grow by dropping the smallest value still in play, so move left up; a too-big sum can only shrink by dropping the largest value, so move right down. Moving the other pointer pushes the sum further from the target.
Running two pointers on an array that isn't sorted. Fix: sort it first if the problem allows, or reach for a different approach (like a hash map for the general Two Sum) — without sorted order, moving a pointer doesn't reliably raise or lower the sum, so the whole "narrow the range" logic falls apart.
Using left <= right as the loop condition instead of left < right. Fix: keep the strict < — with <=, the loop can let left and right land on the same index and compare an element to itself, which is rarely what the problem asks for.
Forgetting to move a pointer at all inside a branch, leaving the range unchanged and looping forever. Fix: double-check every branch either returns an answer or advances exactly one pointer before looping back.

Ko'p Uchraydigan Xatolar

Yig'indi target'ga mos kelmaganda noto'g'ri pointer'ni siljitish — masalan, yig'indi kichik bo'lganda rightni orqaga tortish. Yechim: saralangan tartibdan xulosa chiqaring — juda kichik yig'indi faqat hozircha ishtirokdagi eng kichik qiymatni tashlab yuborish orqali o'sishi mumkin, shuning uchun leftni oldinga suring; juda katta yig'indi faqat eng katta qiymatni tashlab yuborish orqali kichrayishi mumkin, shuning uchun rightni orqaga torting. Boshqa pointer'ni siljitish yig'indini target'dan yanada uzoqlashtiradi.
Two pointers'ni saralanmagan array'da ishlatish. Yechim: masala ruxsat bersa avval saralang, yoki boshqa yondashuvga murojaat qiling (masalan, umumiy Two Sum uchun hash map) — saralangan tartib bo'lmasa, pointer'ni siljitish yig'indini ishonchli tarzda oshirmaydi yoki kamaytirmaydi, shuning uchun butun "maydonni toraytirish" mantig'i buziladi.
Loop shartida left < right o'rniga left <= right ishlatish. Yechim: qat'iy <ni saqlang — <= bilan, loop left va rightni bitta indeksga tushirib, elementni o'zi bilan solishtirishga yo'l qo'yishi mumkin, bu esa masala talabiga kamdan-kam mos keladi.
Biror tarmoq ichida pointer'ni umuman siljitishni unutish — bu maydonni o'zgarishsiz qoldirib, cheksiz loop'ga olib keladi. Yechim: loop qaytishdan oldin har bir tarmoq javob qaytarishini yoki aynan bitta pointer'ni siljitishini qayta tekshiring.

When to Use It

The input is already sorted, or can be sorted cheaply up front, and you need a pair (or triplet, in problems like 3Sum) whose sum, difference, or product hits a target — two pointers exploits the fact that moving one pointer has a predictable, monotonic effect on that value.
You'd otherwise reach for a nested loop checking every pair — O(n²) — and want to cut it down to a single O(n) pass by narrowing the range from both ends instead of checking every combination.
Classic shapes: pair-sum-equals-target (Two Sum II), maximizing an area or capacity bounded by two ends (Container With Most Water), or partitioning and compacting an array in place (removing duplicates, reversing in place).
Skip it when the array isn't sorted and can't be, or when the problem needs every matching pair or subset rather than narrowing toward one answer — a hash map or different traversal usually fits those better.

Qachon Ishlatish Kerak

Kirish ma'lumoti allaqachon saralangan, yoki arzon narxda oldindan saralanishi mumkin, va sizga yig'indisi, ayirmasi yoki ko'paytmasi target'ga teng bo'lgan juftlik (yoki 3Sum kabi masalalarda uchlik) kerak — two pointers bitta pointer'ni siljitish o'sha qiymatga bashorat qilinadigan, monoton ta'sir ko'rsatishidan foydalanadi.
Aks holda har bir juftlikni tekshiradigan nested loop — O(n²) — ishlatgan bo'lardingiz, va har bir kombinatsiyani tekshirish o'rniga maydonni ikkala uchidan toraytirib, bitta O(n) pass'ga tushirmoqchisiz.
Klassik shakllar: juftlik yig'indisi target'ga teng (Two Sum II), ikki uch bilan chegaralangan maydon yoki sig'imni maksimallashtirish (Container With Most Water), yoki array'ni joyida bo'lish va siqish (dublikatlarni olib tashlash, joyida teskari aylantirish).
Array saralanmagan va saralanishi mumkin bo'lmasa, yoki masala bitta javobga toraytirish o'rniga har bir mos juftlik yoki subset'ni talab qilsa, undan saqlaning — bunday hollarda odatda hash map yoki boshqa traversal yaxshiroq mos keladi.

LeetCode Practice

167. Two Sum II - Input Array Is Sorted ↗

Restated: given a 1-indexed array numbers sorted in non-decreasing order and an integer target, find two numbers that add up to target and return their 1-indexed positions as [index1, index2] with index1 < index2. Exactly one valid pair is guaranteed to exist.

Spot the shape. Sorted array, looking for a pair whose sum hits an exact target — that's the pair-sum pattern two pointers was built for, instead of an O(n²) check of every pair.
Set up the pointers. left, right = 0, len(numbers) - 1 — using ordinary 0-indexed positions internally, even though the array itself is described as 1-indexed.
Loop and compare. While left < right, compute total = numbers[left] + numbers[right] and compare it to target.
Branch exactly as worked out above. Equal → found it. Too small → left += 1. Too big → right -= 1.
Convert back to 1-indexed before returning. LeetCode wants positions, not 0-indexed array indices, so the answer is [left + 1, right + 1], not [left, right] — an easy detail to forget since the pointer logic itself is entirely 0-indexed.

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1

    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]  # LeetCode expects 1-indexed positions
        elif total < target:
            left += 1    # sum too small: only a bigger left value can raise it
        else:
            right -= 1   # sum too big: only a smaller right value can lower it

    return []  # no pair sums to target (LC guarantees one exists, so this won't trigger)

LeetCode Amaliyoti