Problem link ও উৎস
- **Original source:** LeetCode Two Sum II — Input Array Is Sorted; CSES Sum of Two Values
- **Platform:** LeetCode —
; CSES —
- **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 পথ — তুলনাটাই শিক্ষা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **sorted** (ছোট থেকে বড়) array `a` আর একটা `target` সংখ্যা দেওয়া আছে। তোমাকে এমন **দুটো index** `(i, j)` খুঁজতে হবে যাদের `a[i] + a[j] == target`, যেখানে `i < j`। ঠিক একটাই উত্তর আছে ধরে নাও; না পেলে `None`।
মূল কথা: array sorted — এই তথ্যটাকে কাজে লাগানোই এই problem-এর প্রাণ। Unsorted হলে এই কৌশল খাটত না (তখন 073-এর hash map পথ লাগত)।
### Input ও output {#6-example-input-and-output}
```text
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` (জুটিই হয় না)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা লম্বা বইয়ের তাক, বাঁ থেকে ডানে বইগুলো **দাম অনুযায়ী সাজানো** (সস্তা থেকে দামি)। তোমাকে ঠিক `target` টাকায় দুটো বই কিনতে হবে।
তুমি এক হাত রাখলে সবচেয়ে সস্তা বইয়ে (বাঁ প্রান্ত), আরেক হাত সবচেয়ে দামি বইয়ে (ডান প্রান্ত)। দুটোর দাম যোগ করলে:
- যোগফল বেশি? → দামি হাতটা একটু বাঁয়ে সরাও (একটু সস্তা বই নাও)
- যোগফল কম? → সস্তা হাতটা একটু ডানে সরাও (একটু দামি বই নাও)
প্রতি step-এ তুমি একটা প্রান্তের বই বাদ দিয়ে দিচ্ছ — আর সেই বইটা আর কখনো লাগবে না। এই "বাদ দিলে আর ফিরব না" ব্যাপারটাই two pointers-কে দ্রুত করে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **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
কোন তথ্য হাতে আছে, তার উপর হাতিয়ার বদলায় — এই বিচারটাই বড় শিক্ষা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **monotonicity** (একমুখী আচরণ)। Array sorted বলে:
- বাঁ পয়েন্টার ডানে সরালে (`l += 1`) যোগফল **বাড়ে** (বড় সংখ্যা ঢুকল)
- ডান পয়েন্টার বাঁয়ে সরালে (`r -= 1`) যোগফল **কমে** (বড় সংখ্যা বেরোল)
মানে দুই প্রান্তের sum-টা একটা "নব"-এর মতো — দুই দিকে ঘুরিয়ে target-এর দিকে নেওয়া যায়। এই predictable আচরণই O(n²)-কে O(n)-এ নামায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে যেটা মাথায় আসে — সব জোড়া ধরে ধরে দেখা:
```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-এর সুবিধাটা একদম ব্যবহারই করছি না।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
বাইরের loop n বার, ভেতরেরটা গড়ে n/2 বার — মোট প্রায় n²/2 জোড়া। n = 100000 হলে প্রায় ৫০০ কোটি operation — interview-তে Time Limit Exceeded।
```text
n = 100000 হলে:
brute force : ~5,000,000,000 জোড়া যাচাই (O(n²), ধীর)
two pointers: বড়জোর 100000 step (O(n), দ্রুত)
```
মূল অপচয়: sorted array-তে আমরা জানি কোন দিকে গেলে sum বাড়বে/কমবে — তবু brute force সেই জ্ঞান ফেলে সব জোড়া ঘাঁটছে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল 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`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **সব জোড়া দেখার দরকার নেই — শুধু দুই প্রান্ত দেখে এক প্রান্ত নিরাপদে ছেঁটে ফেলা যায়।**
প্রতি step-এ ঠিক একটা element চিরতরে বিদায় নেয়। n টা element, প্রতিটা বড়জোর একবার বাদ পড়ে → মোট n step → O(n)। দ্বিমাত্রিক খোঁজ (সব জোড়া) এক মাত্রায় (এক pass) নেমে এল।
### ছবিতে বোঝা {#5-visual-explanation}
দুই আঙুল কীভাবে ভেতরের দিকে আসে, একটা example-এ দেখো (`a = [1, 3, 4, 6, 9]`, `target = 7`):
```text
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-এ অন্তত ১ ঘর সংকুচিত হয়:
```text
sum বড় হলে: [ l ............... r ] → [ l ............ r ] (r বাঁয়ে)
sum ছোট হলে: [ l ............... r ] → [ l ......... r ] (l ডানে)
সমান হলে : থামো — উত্তর পেয়ে গেছ
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`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 হতে পারে না, তাই ফিরে দেখার দরকার নেই।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
l, r = 0, len(a) - 1
```
দুটো আঙুল বসালাম — `l` একদম বাঁয়ে (সবচেয়ে ছোট), `r` একদম ডানে (সবচেয়ে বড়)।
```text
while l < r:
```
দুজন না মেলা পর্যন্ত চলবে। `l == r` হলে একই element, জুটি হয় না — তাই strict `<`।
```text
s = a[l] + a[r]
if s == target: return (l, r)
```
দুই প্রান্তের যোগফল। target-এর সমান হলে সাথে সাথে উত্তর।
```text
if s > target: r -= 1
else: l += 1
```
বেশি হলে বড় দিক ছাঁটো (`r--`), কম হলে ছোট দিক ছাঁটো (`l++`)। প্রতি বার এক প্রান্ত নিশ্চিতভাবে বাদ।
```text
return None
```
while শেষ মানে দুজন মিশে গেছে, কোনো জুটি মেলেনি।
`two_sum_brute` শুধু test যাচাইয়ের reference; বাকি `assert` গুলো নিজেদের চেক করে, সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
(0, 4)
(2, 3)
None
সব test pass!
```
প্রথম দুই লাইন দুটো সফল খোঁজ থেকে; তৃতীয় লাইন `None` কারণ `[1, 2, 3]`-এ যোগফল 7 হওয়ার জুটি নেই। তার আগের সব `assert` (brute-force মেলানো সহ) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — প্রতি step-এ `l` বাড়ে বা `r` কমে, মানে window অন্তত ১ ঘর সংকুচিত হয়। মোট সংকোচন বড়জোর n বার, তাই বড়জোর n step। (Sorted না থাকলে আগে sort লাগত — তখন O(n log n); এখানে input sorted ধরা।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `l`, `r`, `s` — গুটিকয় variable। 073-এর hash map পথে O(n) space লাগত; sorted হওয়ায় এখানে বাড়তি জায়গা প্রায় শূন্য — এটাই pointer পথের বড় সুবিধা।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **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++` — মনে রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode 3Sum** (