081 — Two Sum Sorted

এই note দিয়ে তুমি two pointers পরিবারের জন্মস্থানে পা রাখছ। আগের level-এ Two Sum-কে আমরা hash map দিয়ে সামলেছি; এখানে array আগে থেকে sorted — আর এই একটা শর্ত পুরো খেলা বদলে দেয়। দুই প্রান্ত থেকে দুটো আঙুল রেখে আমরা প্রতি step-এ search space নিশ্চিতভাবে ছোট করব। ধীরে পড়ো — "কেন একটা move নিরাপদ" এই যুক্তিটাই এখানকার আসল রত্ন।

Problem link ও উৎস

• Original source: LeetCode Two Sum II — Input Array Is Sorted; CSES Sum of Two Values
• Platform: LeetCode — https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/; CSES — https://cses.fi/problemset/task/1640
• Topic: Two pointers → opposite-end scan on sorted array
• Difficulty: Easy
• Pattern: opposite pointers (দুই প্রান্ত থেকে চাপা)
• Basic idea inherited from: 073 — Subarray Sum Equals K (ওখানে hash map পথ, এখানে sorted-এ pointer পথ — তুলনাটাই শিক্ষা)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা sorted (ছোট থেকে বড়) array a আর একটা target সংখ্যা দেওয়া আছে। তোমাকে এমন দুটো index (i, j) খুঁজতে হবে যাদের a[i] + a[j] == target, যেখানে i < j। ঠিক একটাই উত্তর আছে ধরে নাও; না পেলে None।

মূল কথা: array sorted — এই তথ্যটাকে কাজে লাগানোই এই problem-এর প্রাণ। Unsorted হলে এই কৌশল খাটত না (তখন 073-এর hash map পথ লাগত)।

Input ও output

উদাহরণ

a (sorted)            target  ->  output
----------------------------------------
[1, 3, 4, 6, 9]         10    ->  (0, 4)   (1 + 9)
[1, 3, 4, 6, 9]          7    ->  (0, 3)   (1 + 6)
[2, 3, 4]                6    ->  (0, 2)   (2 + 4)
[2, 7, 11, 15]          26    ->  (2, 3)   (11 + 15)
[1, 2]                   3    ->  (0, 1)
[1, 2, 3]               7    ->  None      (কোনো জুটি নেই)

Edge case: জুটি না থাকলে None; দুইয়ের কম element থাকলেও None (জুটিই হয় না)।

চেনা উদাহরণে বোঝা

ভাবো একটা লম্বা বইয়ের তাক, বাঁ থেকে ডানে বইগুলো দাম অনুযায়ী সাজানো (সস্তা থেকে দামি)। তোমাকে ঠিক target টাকায় দুটো বই কিনতে হবে।

তুমি এক হাত রাখলে সবচেয়ে সস্তা বইয়ে (বাঁ প্রান্ত), আরেক হাত সবচেয়ে দামি বইয়ে (ডান প্রান্ত)। দুটোর দাম যোগ করলে:

• যোগফল বেশি? → দামি হাতটা একটু বাঁয়ে সরাও (একটু সস্তা বই নাও)
• যোগফল কম? → সস্তা হাতটা একটু ডানে সরাও (একটু দামি বই নাও)

প্রতি step-এ তুমি একটা প্রান্তের বই বাদ দিয়ে দিচ্ছ — আর সেই বইটা আর কখনো লাগবে না। এই "বাদ দিলে আর ফিরব না" ব্যাপারটাই two pointers-কে দ্রুত করে।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা দাঁড়িয়ে আছে 073 — Subarray Sum Equals K-এর কাঁধে। 073-এ আমরা "দুটো জিনিসের সম্পর্ক" খুঁজতে hash map ব্যবহার করেছি — প্রতিটা element দেখে জিজ্ঞেস করেছি "এর জুটি আগে দেখেছি কি?"।

এখানে array sorted বলে hash map-এর দরকারই নেই — sorted-এর structure নিজেই জুটি খুঁজে দেয়। তাই এই note আসলে একটা তুলনা শেখায়:

• Unsorted + index দরকার → hash map (073-এর পথ), O(n) time + O(n) space
• Sorted → opposite pointers (এই পথ), O(n) time + O(1) space

কোন তথ্য হাতে আছে, তার উপর হাতিয়ার বদলায় — এই বিচারটাই বড় শিক্ষা।

ভেতরের অঙ্ক

মূল idea হলো monotonicity (একমুখী আচরণ)। Array sorted বলে:

• বাঁ পয়েন্টার ডানে সরালে (l += 1) যোগফল বাড়ে (বড় সংখ্যা ঢুকল)
• ডান পয়েন্টার বাঁয়ে সরালে (r -= 1) যোগফল কমে (বড় সংখ্যা বেরোল)

মানে দুই প্রান্তের sum-টা একটা "নব"-এর মতো — দুই দিকে ঘুরিয়ে target-এর দিকে নেওয়া যায়। এই predictable আচরণই O(n²)-কে O(n)-এ নামায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথমে যেটা মাথায় আসে — সব জোড়া ধরে ধরে দেখা:

Python

def two_sum_brute(a, target):
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] + a[j] == target:
                return (i, j)
    return None

এটা ঠিক উত্তর দেয়, sorted না হলেও চলে। কিন্তু এখানে sorted-এর সুবিধাটা একদম ব্যবহারই করছি না।

কোথায় বেশি কাজ হতে পারে

বাইরের loop n বার, ভেতরেরটা গড়ে n/2 বার — মোট প্রায় n²/2 জোড়া। n = 100000 হলে প্রায় ৫০০ কোটি operation — interview-তে Time Limit Exceeded।

উদাহরণ

n = 100000 হলে:
  brute force : ~5,000,000,000 জোড়া যাচাই   (O(n²), ধীর)
  two pointers: বড়জোর 100000 step           (O(n), দ্রুত)

মূল অপচয়: sorted array-তে আমরা জানি কোন দিকে গেলে sum বাড়বে/কমবে — তবু brute force সেই জ্ঞান ফেলে সব জোড়া ঘাঁটছে।

আরও ভালোভাবে ভাবা

মূল insight: sorted বলে দুই প্রান্তের sum দেখে নিশ্চিতভাবে বলা যায় কোন প্রান্ত বাদ দেওয়া নিরাপদ।

a[l] + a[r] > target হলে — a[r] খুব বড়। a[r]-এর জুটি হতে পারে শুধু a[l] বা তার ডানের কেউ, কিন্তু তারা সবাই a[l]-এর সমান বা বড়, তাই sum আরো বেশি হবে। মানে a[r]-এর কোনো বৈধ জুটিই নেই → a[r] চিরতরে বাদ → r -= 1। উল্টোভাবে sum ছোট হলে a[l] বাদ → l += 1।

ভাবনার পরিবর্তন

আসল "আহা!" মুহূর্ত: সব জোড়া দেখার দরকার নেই — শুধু দুই প্রান্ত দেখে এক প্রান্ত নিরাপদে ছেঁটে ফেলা যায়।

প্রতি step-এ ঠিক একটা element চিরতরে বিদায় নেয়। n টা element, প্রতিটা বড়জোর একবার বাদ পড়ে → মোট n step → O(n)। দ্বিমাত্রিক খোঁজ (সব জোড়া) এক মাত্রায় (এক pass) নেমে এল।

ছবিতে বোঝা

দুই আঙুল কীভাবে ভেতরের দিকে আসে, একটা example-এ দেখো (a = [1, 3, 4, 6, 9], target = 7):

উদাহরণ

a = [ 1 ,  3 ,  4 ,  6 ,  9 ]
      ^                   ^
      l                   r        a[l]+a[r] = 1+9 = 10 > 7  → r--

a = [ 1 ,  3 ,  4 ,  6 ,  9 ]
      ^              ^
      l              r            a[l]+a[r] = 1+6 = 7  == 7  → পাওয়া গেল! (0, 3)

প্রতিটা তীর ভেতরে এসে search space ছোট করছে। মোট window-টা প্রতি step-এ অন্তত ১ ঘর সংকুচিত হয়:

উদাহরণ

sum বড় হলে:  [ l ............... r ]  →  [ l ............ r ]   (r বাঁয়ে)
sum ছোট হলে:  [ l ............... r ]  →  [    l ......... r ]   (l ডানে)
সমান হলে   :  থামো — উত্তর পেয়ে গেছ

ছোট input-এ ধাপে ধাপে

a = [1, 3, 4, 6, 9], target = 7 ধীরে চালাই:

step	l	r	a[l]	a[r]	sum	তুলনা	action
1	0	4	1	9	10	10 > 7	r -= 1
2	0	3	1	6	7	7 == 7	পাওয়া গেল → return (0, 3)

দুই step-এই উত্তর। লক্ষ করো প্রথম step-এ আমরা index 4 (মান 9)-কে চিরতরে বাদ দিয়েছি — 9-এর সাথে আর কারো জুটি 7 হতে পারে না, তাই ফিরে দেখার দরকার নেই।

কোড ও ব্যাখ্যা

Python

Python

def two_sum_sorted(a, target):
    """sorted array a-তে a[i]+a[j]==target এমন (i, j) ফেরত দেয় (i < j); না পেলে None।"""
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return (l, r)
        if s > target:
            r -= 1
        else:
            l += 1
    return None


def two_sum_brute(a, target):
    """ধীর কিন্তু সরল reference — সব জোড়া যাচাই (test মেলানোর জন্য)।"""
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] + a[j] == target:
                return (i, j)
    return None


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert two_sum_sorted([1, 3, 4, 6, 9], 10) == (0, 4)
assert two_sum_sorted([1, 3, 4, 6, 9], 7) == (0, 3)
assert two_sum_sorted([2, 3, 4], 6) == (0, 2)
assert two_sum_sorted([2, 7, 11, 15], 26) == (2, 3)
assert two_sum_sorted([1, 2], 3) == (0, 1)
assert two_sum_sorted([1, 2, 3], 7) is None
assert two_sum_sorted([5], 5) is None          # একটামাত্র element, জুটি নেই

# brute force-এর সাথে মিলিয়ে দেখা (যেখানে উত্তর আছে)
for tgt in range(2, 19):
    arr = [1, 3, 4, 6, 9]
    fast = two_sum_sorted(arr, tgt)
    slow = two_sum_brute(arr, tgt)
    # দুটোর যেকোনো এক বৈধ জুটি দিলেই হয়; দুজনই None বা দুজনই জুটি
    assert (fast is None) == (slow is None)
    if fast is not None:
        assert arr[fast[0]] + arr[fast[1]] == tgt

print(two_sum_sorted([1, 3, 4, 6, 9], 10))   # (0, 4)
print(two_sum_sorted([2, 7, 11, 15], 26))    # (2, 3)
print(two_sum_sorted([1, 2, 3], 7))          # None
print("সব test pass!")

কোডের প্রতিটি অংশ

উদাহরণ

l, r = 0, len(a) - 1

দুটো আঙুল বসালাম — l একদম বাঁয়ে (সবচেয়ে ছোট), r একদম ডানে (সবচেয়ে বড়)।

উদাহরণ

while l < r:

দুজন না মেলা পর্যন্ত চলবে। l == r হলে একই element, জুটি হয় না — তাই strict <।

উদাহরণ

s = a[l] + a[r]
if s == target: return (l, r)

দুই প্রান্তের যোগফল। target-এর সমান হলে সাথে সাথে উত্তর।

উদাহরণ

if s > target: r -= 1
else:          l += 1

বেশি হলে বড় দিক ছাঁটো (r--), কম হলে ছোট দিক ছাঁটো (l++)। প্রতি বার এক প্রান্ত নিশ্চিতভাবে বাদ।

উদাহরণ

return None

while শেষ মানে দুজন মিশে গেছে, কোনো জুটি মেলেনি।

two_sum_brute শুধু test যাচাইয়ের reference; বাকি assert গুলো নিজেদের চেক করে, সব ঠিক থাকলে শেষে সব test pass! ছাপে।

Output মিলিয়ে দেখা

চালালে ছাপবে:

উদাহরণ

(0, 4)
(2, 3)
None
সব test pass!

প্রথম দুই লাইন দুটো সফল খোঁজ থেকে; তৃতীয় লাইন None কারণ [1, 2, 3]-এ যোগফল 7 হওয়ার জুটি নেই। তার আগের সব assert (brute-force মেলানো সহ) চুপচাপ pass করেছে, তাই শেষে সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(n) — প্রতি step-এ l বাড়ে বা r কমে, মানে window অন্তত ১ ঘর সংকুচিত হয়। মোট সংকোচন বড়জোর n বার, তাই বড়জোর n step। (Sorted না থাকলে আগে sort লাগত — তখন O(n log n); এখানে input sorted ধরা।)

অতিরিক্ত জায়গা

O(1) — শুধু l, r, s — গুটিকয় variable। 073-এর hash map পথে O(n) space লাগত; sorted হওয়ায় এখানে বাড়তি জায়গা প্রায় শূন্য — এটাই pointer পথের বড় সুবিধা।

যে ভুলগুলো এড়াতে হবে

• Unsorted array-তে এই কৌশল চালানো — "sum বড় তাই r--" যুক্তিটা শুধু sorted-এ খাটে। আগে sort নিশ্চিত করো (আর sort করলে original index হারায় — index দরকার হলে সাবধান)।
• while l <= r লেখা — তাহলে l == r-এ একই element নিজের সাথে যোগ হতে পারে, ভুল জুটি। সবসময় l < r।
• পেয়ে যাওয়ার পরেও loop চালিয়ে যাওয়া — match পেলে সাথে সাথে return; না করলে অযথা কাজ বা ভুল।
• sum বাড়ানো-কমানোর দিক উল্টে ফেলা — sum বেশি হলে l++ করলে sum আরো বাড়বে, কখনো মিলবে না। বড় হলে r--, ছোট হলে l++ — মনে রাখো।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

• LeetCode 3Sum (https://leetcode.com/problems/3sum/) — একটা element fix করে বাকি দুটোতে ঠিক এই opposite-pointer খোঁজ (এই repo-র 083)।
• LeetCode Container With Most Water (https://leetcode.com/problems/container-with-most-water/) — আবারো দুই প্রান্ত থেকে চাপা, তবে move-এর যুক্তি ভিন্ন (083 নয়, 084)।
• CSES Sum of Two Values (https://cses.fi/problemset/task/1640) — হুবহু এই problem, তবে index original রাখার চ্যালেঞ্জসহ।

কৌশলটি মনে রাখুন

Opposite two pointers on a sorted array — দুই প্রান্ত থেকে শুরু, sum বড় হলে r--, ছোট হলে l++। পেছনের বড় শিক্ষা: monotonic structure থাকলে এক প্রান্ত দেখে নিশ্চিতভাবে অন্য প্রান্ত ছেঁটে ফেলা যায় — তাই O(n²) নয়, O(n)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "sorted array + জুটি খোঁজা = দুই প্রান্ত থেকে চাপা; sum বড় হলে r--, ছোট হলে l++; প্রতি step-এ এক element চিরতরে বাদ বলে O(n)। Signal: 'sorted' শব্দটা দেখলেই opposite pointers মাথায় আসুক।"

পরের ধাপ → 082 — Pair with Difference K (এবার দুই আঙুল একই দিকে ছুটবে)। তুলনা করো → ../../05-prefix-difference-contribution/problems/073-subarray-sum-equals-k.md (hash পথ vs pointer পথ)।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।