Problem link ও উৎস
- **Original source:** Classic sorted-array pair problem
- **Platform:** LeetCode —
- **Topic:** hash map vs two pointers
- **Difficulty:** Medium
- **Pattern:** complement lookup vs two pointers
- **Basic idea inherited from:** Two Sum — দুটো approach-ই পাশাপাশি রেখে তুলনা করো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **সাজানো (non-decreasing)** সংখ্যার array `numbers` আর একটা `target` দেওয়া আছে। এমন **দুটো position** ফেরত দিতে হবে যাদের সংখ্যা যোগ করলে ঠিক `target` হয়। এখানে একটা ছোট্ট কিন্তু গুরুত্বপূর্ণ শর্ত: উত্তর **1-indexed** (অর্থাৎ প্রথম element-এর position 1, 0 নয়), আর ধরে নাও উত্তর সবসময় একটাই।
```text
numbers = [2, 7, 11, 15], target = 9
2 + 7 = 9 → উত্তর [1, 2] (position, index নয়)
```
### Input ও output {#8-example-input-and-output}
```text
Input : numbers = [2, 7, 11, 15], target = 9 Output: [1, 2]
Input : numbers = [2, 3, 4], target = 6 Output: [1, 3]
Input : numbers = [-1, 0], target = -1 Output: [1, 2]
Edge : numbers = [5, 25, 75], target = 100 Output: [2, 3]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা সাজানো দামের তালিকা ধরে তুমি ঠিক 9 টাকার দুটো জিনিস কিনতে চাও। বাঁ দিক থেকে সবচেয়ে সস্তা আর ডান দিক থেকে সবচেয়ে দামি জিনিসে আঙুল রাখো। যোগফল বেশি হলে দামি আঙুলটা একটু সস্তার দিকে সরাও; কম হলে সস্তা আঙুলটা একটু দামির দিকে সরাও। দুই আঙুল মাঝখানে এসে মিললেই জোড়া পেয়ে গেছ — পুরো তালিকা বারবার পড়তে হলো না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Two Sum** (এই tracker-এর #1)-এর উপর দাঁড়িয়ে। সেখানে array এলোমেলো ছিল, তাই hash map দিয়ে complement মনে রাখা ছাড়া উপায় ছিল না। এখানে নতুন তথ্য একটাই — array **sorted**। এই একটা শব্দ পুরো খেলা বদলে দেয়: এখন তুমি দুটো রাস্তায় যেতে পারো, আর সেই দুটো তুলনা করাই এই note-এর আসল শিক্ষা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই স্তরের। প্রথম স্তর Two Sum-এর মতোই: `a + b = target` মানে `a`-র partner ঠিক `target - a`। দ্বিতীয় স্তর sorted-হওয়া থেকে আসে — যদি দুই প্রান্ত থেকে দুটো সংখ্যা নাও আর তাদের যোগফল `target`-এর চেয়ে **বড়** হয়, তাহলে বড় প্রান্তটা ছোট করলেই যোগফল কমবে; **ছোট** হলে ছোট প্রান্তটা বড় করলে যোগফল বাড়বে। অর্থাৎ প্রতিটা তুলনা একটা possibility একেবারে ছেঁটে ফেলে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো বিকল্প:
- **Two pointers:** কোনো extra structure লাগে না — শুধু দুটো index `lo` আর `hi`। কাজ করে কারণ array sorted।
- **Hash map** (`dict`, value → position): Two Sum-এর হুবহু রাস্তা, sorted-হওয়াকে উপেক্ষা করে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Sorted array-তে two pointers একদম মানানসই, কারণ ক্রমটাই তোমাকে বলে দেয় কোন দিকে সরতে হবে — তাই **O(1) extra space**-এই কাজ শেষ। Hash map-ও কাজ করে আর গড়ে O(1) lookup দেয়, কিন্তু O(n) extra জায়গা খায় যেটা এখানে অপ্রয়োজনীয়। মূল শিক্ষা: input-এর গঠন (sorted) জানা থাকলে data structure-এর খরচ কমানো যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা Two Sum-এর মতোই: প্রতিটা জোড়া (i, j) ধরে দেখো যোগফল target কি না।
```text
প্রতিটা i-র জন্য:
প্রতিটা j > i-র জন্য:
numbers[i] + numbers[j] == target হলে return [i+1, j+1]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে **O(n^2)**। আর এখানে অপচয়টা আরও দৃষ্টিকটু, কারণ array sorted — অর্থাৎ ক্রমটা একটা বিনামূল্যের ইঙ্গিত দিচ্ছে কোন দিকে partner আছে, অথচ brute force সেই ইঙ্গিত পুরো ফেলে দিয়ে সব জোড়া পরীক্ষা করছে। জানা গঠন কাজে না লাগানোই এখানে আসল ভুল।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **sorted মানে দিক জানা**। দুই প্রান্তের যোগফল target থেকে বড় হলে উত্তর আরও বাঁয়ে; ছোট হলে আরও ডানে। তাই প্রতিটা তুলনায় অন্তত একটা সংখ্যা চিরতরে বাদ পড়ে — খোঁজার জায়গা প্রতি ধাপে এক ঘর সংকুচিত হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`lo` আর `hi` দুই প্রান্তে বসাও। যোগফল দেখো: সমান হলে জোড়া পেয়ে গেছ (1-indexed করে ফেরত দাও); বেশি হলে `hi` কমাও; কম হলে `lo` বাড়াও। `lo` আর `hi` মাঝখানে এসে মেলা পর্যন্ত চালাও — এক pass, **O(n) time, O(1) space**। বিকল্পে Two Sum-এর hash map রাস্তাও কাজ করে (O(n) time কিন্তু O(n) space) — sorted-হওয়াকে কাজে না লাগিয়ে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *sorted শুনলেই দুই প্রান্ত থেকে চাপ দেওয়ার কথা ভাবো।* Two Sum-এ tweak ছিল "search না করে remember করো"; এখানে sorted-হওয়া আরও সস্তা একটা tweak খুলে দেয় — "remember করারও দরকার নেই, ক্রম ধরে দুদিক থেকে এগোও"। একই problem, কম জায়গা।
### ছবিতে বোঝা {#7-visual-explanation}
`numbers = [2, 7, 11, 15]`, `target = 9`। `lo` বাঁ থেকে, `hi` ডান থেকে চাপ দেয়:
```text
lo=0(2) hi=3(15) s=2+15=17 > 9 → hi-- (বড় দিকটা ছোট করো)
lo=0(2) hi=2(11) s=2+11=13 > 9 → hi--
lo=0(2) hi=1(7) s=2+7 =9 == 9 → return [lo+1, hi+1] = [1, 2]
```
প্রতিবার একটা প্রান্ত নড়ছে, আর প্রতিটা নড়া পুরো একটা সারি বা কলামের possibility বাদ দিচ্ছে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `numbers = [2, 3, 4]`, `target = 6`:
1. শুরু: `lo = 0` (মান 2), `hi = 2` (মান 4)।
2. `s = 2 + 4 = 6`; `6 == 6` → জোড়া পেয়ে গেছি।
3. return `[lo + 1, hi + 1] = [1, 3]`।
4. শেষ: উত্তর `[1, 3]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def two_sum_two_pointers(numbers, target):
lo, hi = 0, len(numbers) - 1 # দুই প্রান্ত থেকে চাপ দাও
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # problem 1-indexed উত্তর চায়
elif s < target:
lo += 1 # যোগফল ছোট → বড় দিকে সরো
else:
hi -= 1 # যোগফল বড় → ছোট দিকে সরো
return []
def two_sum_hash(numbers, target):
seen = {} # value -> 1-indexed position
for i, x in enumerate(numbers):
need = target - x
if need in seen:
return [seen[need], i + 1]
seen[x] = i + 1
return []
# ---- tests ----
for solve in (two_sum_two_pointers, two_sum_hash):
assert solve([2, 7, 11, 15], 9) == [1, 2]
assert solve([2, 3, 4], 6) == [1, 3]
assert solve([-1, 0], -1) == [1, 2]
assert solve([1, 2, 3, 4, 4, 9, 56, 90], 8) == [4, 5]
assert solve([5, 25, 75], 100) == [2, 3]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `lo, hi = 0, len(numbers) - 1` — দুই প্রান্তে দুটো pointer বসাই।
- `while lo < hi` — যতক্ষণ তারা পরস্পরকে পার না করছে।
- `s = numbers[lo] + numbers[hi]` — এই মুহূর্তের জোড়ার যোগফল।
- `if s == target: return [lo + 1, hi + 1]` — মিলে গেলে 1-indexed করে ফেরত।
- `elif s < target: lo += 1` — কম পড়েছে, বড় মানের দিকে সরি।
- `else: hi -= 1` — বেশি হয়েছে, ছোট মানের দিকে সরি।
- দ্বিতীয় function `two_sum_hash` — Two Sum-এর হুবহু complement lookup, শুধু position 1-indexed করা; sorted-হওয়াকে এটা ব্যবহারই করে না।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
দুটো function-ই একই উত্তর দেয়, তাই test একটা loop-এ দুটোকেই যাচাই করে। `[2,7,11,15]` target 9-এ two-pointer `hi` দুবার কমে 7-এ এসে থামে → `[1, 2]`; hash রাস্তা `7`-এ এসে `2` আগে দেখা পায় → `[1, 2]`। `[2,3,4]` target 6 → `[1, 3]`। `[-1,0]` target -1 → `[1, 2]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
দুটো রাস্তাই **O(n)** — two pointers এক pass-এ array scan করে; hash map-ও এক pass, প্রতি element-এ গড়ে O(1) operation।
### অতিরিক্ত জায়গা {#19-space-complexity}
এখানেই পার্থক্য: two pointers **O(1)** extra (শুধু দুটো index), কিন্তু hash map **O(n)** extra (সব দেখা value জমে)। Sorted-হওয়াকে কাজে লাগিয়ে আমরা space O(n) থেকে O(1)-এ নামালাম।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- 1-indexing ভুলে যাওয়া — problem position চায়, index নয়; `+1` বাদ দিলে উত্তর এক ঘর সরে যায়।
- sorted-হওয়া উপেক্ষা করে শুধু hash map লেখা — কাজ করবে, কিন্তু interview-তে "sorted দেখে কী সুবিধা পেলে?" প্রশ্নের উত্তর হারাবে।
- `while lo < hi`-র বদলে `lo <= hi` লেখা — তখন একই element নিজের সাথে জোড়া বানিয়ে ভুল করতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Two Sum (#1)-এর complement lookup। নতুন সংযোজন হলো sorted-array-এর two-pointer চাল, যা arrays section-এর "দুই প্রান্ত থেকে এগোনো" idea-র সাথে এই chapter-এর pair-thinking মিশিয়ে দেয়। [../patterns.md](../patterns.md)-র Pattern 2 (complement lookup)-ই এর মূল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Two Sum —