Problem link ও উৎস
- **Original source:** Classic sort + two-pointer exercise
- **Platform:** LeetCode —
- **Topic:** array / two pointers
- **Difficulty:** Medium
- **Pattern:** sort + two pointers (একটা element fix করে বাকি দুটো pair-sum)
- **Basic idea inherited from:** pair sum (problem 2) — একটা element fix করে, বাকি array-তে দুটোর যোগফল খোঁজা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া। এমন সব **unique triple** (তিনটা ভিন্ন index) খুঁজে বের করো যাদের তিন value-র যোগফল ঠিক 0। উত্তরে একই triple দুবার থাকা যাবে না। triple-গুলোর list ফেরত দাও।
```text
nums = [-1, 0, 1, 2, -1, -4]
0 হয় এমন triple: [-1, -1, 2] আর [-1, 0, 1]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [-1, 0, 1, 2, -1, -4] -> [[-1, -1, 2], [-1, 0, 1]]
Input : [0, 1, 1] -> [] (0 হয় এমন triple নেই)
Edge case 1 (সব শূন্য): [0, 0, 0] -> [[0, 0, 0]]
Edge case 2 (duplicate শূন্য): [0, 0, 0, 0] -> [[0, 0, 0]] (একবারই)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তিনজনের ওজন মিলে ঠিক শূন্য (ঋণ-ধন ভারসাম্য) চাই। একজনকে আগে বেছে নাও; এখন বাকিদের সারিতে দাঁড় করিয়ে (sorted) দুই প্রান্ত থেকে দুজনকে ধরো। তাদের যোগফল কম হলে বাঁয়ের জনকে ভারীজনে বদলাও, বেশি হলে ডানের জনকে হালকাজনে — মাঝে মিলে গেলে triple পেলে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত **pair sum** (Two Sum, problem 2)। একটা element `nums[i]` fix করলে বাকিটা হয়ে যায় "এমন দুটো সংখ্যা খুঁজি যাদের যোগফল `-nums[i]`" — অর্থাৎ একটা two-sum। array sort করে নিলে সেই two-sum-টা converging two pointers দিয়ে O(n)-এ করা যায়। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 1 — Two Pointers" দেখো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: `a + b + c = 0` মানে একটা fix করলে `b + c = -a`। sorted array-তে দুই pointer (`left`, `right`)-এর sum target-এর চেয়ে ছোট হলে `left` ডানে (sum বাড়ে), বড় হলে `right` বাঁয়ে (sum কমে) — প্রতিটা move একটা candidate চিরতরে বাদ দেয়। duplicate এড়াতে sorted order কাজে লাগে: পাশাপাশি সমান value skip করলেই unique triple।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো ভারী structure লাগে না — array-টা **sort** করি (O(n log n)), তারপর প্রতিটা fixed element-এ **দুটো integer pointer**। উত্তর জমাতে একটা result list। sort বাদে O(1) extra।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Sort করার পর array-র order-ই duplicate detection আর two-pointer movement দুটোকেই সম্ভব করে: সমান value পাশাপাশি আসে (skip সহজ), আর sum ছোট/বড় হলে কোন দিকে সরতে হবে তা নিশ্চিত। O(1) random access-এ দুই pointer-এর value সাথে সাথে পড়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: তিনটা nested loop দিয়ে সব triple `(i, j, l)` try করো, যোগফল 0 হলে রাখো, আর শেষে duplicate বাদ দাও।
```text
res = set()
for i in range(n):
for j in range(i+1, n):
for l in range(j+1, n):
if nums[i] + nums[j] + nums[l] == 0:
res.add(sorted triple)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
তিনটা nested loop মানে **O(n^3)** — array একটু বড় হলেই অসম্ভব ধীর। উপরন্তু duplicate সামলাতে আলাদা set লাগে। sort + two-pointer দিয়ে এটা O(n^2)-এ নামে আর duplicate-ও sorted order থেকেই handle হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা element fix করলে বাকিটা একটা two-sum (`-nums[i]` target)। sorted array-তে two-sum দুই pointer দিয়ে O(n); তাই মোট O(n^2)। আর sorted বলে পাশাপাশি সমান value skip করলেই unique triple — আলাদা dedup structure লাগে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
array sort করো। প্রতিটা index `i` (fixed first element)-এ: যদি `nums[i] == nums[i-1]` হয় তবে skip (duplicate fixed); `nums[i] > 0` হলে break (sorted-এ সবচেয়ে ছোটটাই positive মানে আর 0 হবে না)। তারপর `left=i+1`, `right=n-1` নিয়ে two-pointer: sum 0-র চেয়ে ছোট → `left++`, বড় → `right--`, সমান → triple রাখো আর দুই pointer-এর duplicate skip করো। মোট O(n^2)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "তিনটা loop ঘোরাব" (O(n^3)) ভুলে গিয়ে ভাবো "একটা fix করি, বাকিটা sorted two-sum।" তিন-যোগফলের সমস্যা ভেঙে যায় চেনা pair-sum-এ, আর sort duplicate-ও সামলে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
Sorted input `[-4,-1,-1,0,1,2]`। L/R হলো index; প্রতিটি সিদ্ধান্ত নিচে আছে।
| fixed index/value | L,R | মোট | কাজ |
| --- | --- | --- | --- |
| 0 / -4 | 1,5 | -3 | L=2 |
| 0 / -4 | 2,5 | -3 | L=3 |
| 0 / -4 | 3,5 | -2 | L=4 |
| 0 / -4 | 4,5 | -1 | L=5; এই fixed index শেষ |
| 1 / -1 | 2,5 | 0 | `[-1,-1,2]` record; L=3,R=4 |
| 1 / -1 | 3,4 | 0 | `[-1,0,1]` record; L=4,R=3; শেষ |
| 2 / -1 | — | — | আগের fixed value-এর সমান: skip |
| 3 / 0 | 4,5 | 3 | R=4; শেষ |
এর পরে তিনটি element বেছে নেওয়ার মতো suffix নেই। ফল `[[−1,−1,2],[−1,0,1]]`।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[0, 0, 0, 0]` (sort করেও একই):
1. `i=0` (`nums[0]=0`): `left=1`, `right=3`। sum `0+0+0=0` → triple `[0,0,0]` রাখি; `left=2`, `right=2`; দুই pointer-এর duplicate skip-এ `left < right` মিথ্যা → ভেতরের loop শেষ।
2. `i=1` (`nums[1]=0`): `nums[1] == nums[0]` → duplicate fixed, `continue`।
3. `i=2`: range শেষ (`range(n-2)=range(2)` শুধু `i=0,1`)।
4. ফল: `[[0, 0, 0]]` (একবারই)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def three_sum(nums):
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # একই fixed element আবার নয়
if nums[i] > 0:
break # সবচেয়ে ছোটটাই positive -> আর 0 হবে না
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1 # sum বাড়াতে left ডানে
elif total > 0:
right -= 1 # sum কমাতে right বাঁয়ে
else:
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1 # duplicate left skip
while left < right and nums[right] == nums[right + 1]:
right -= 1 # duplicate right skip
return res
# ---- tests ----
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 1, 1]) == []
assert three_sum([0, 0, 0]) == [[0, 0, 0]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `nums.sort()` — duplicate skip আর two-pointer দুটোর জন্য sorted order জরুরি।
- `for i in range(n - 2)` — fixed first element; শেষ দুটো left/right-এর জন্য রাখা।
- `if i > 0 and nums[i] == nums[i-1]: continue` — একই value আবার fix করলে repeat triple আসত।
- `if nums[i] > 0: break` — sorted-এ এখান থেকে সব positive, তিন positive-এর যোগ কখনো 0 নয়।
- `total = ...` — fixed + দুই pointer-এর যোগফল।
- `total < 0 → left += 1`, `total > 0 → right -= 1` — sorted বলে এই move গুলো sum-কে target-এর দিকে ঠেলে।
- `else:` triple রাখি, দুই pointer ভেতরে আনি, আর পাশের সমান value গুলো skip করে duplicate triple এড়াই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[-1,0,1,2,-1,-4]` sort হয়ে `[-4,-1,-1,0,1,2]`; fix `-1`-এ `[-1,-1,2]` ও `[-1,0,1]`, পরের `-1` skip → `[[-1,-1,2],[-1,0,1]]`, assert pass। `[0,1,1]` → কোনো 0-যোগ triple নেই, `[]`; `[0,0,0]` ও `[0,0,0,0]` → দুটোতেই `[[0,0,0]]` একবার। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
sort + two-pointer; JS-এ অবশ্যই numeric comparator `(a,b)=>a-b` লাগবে।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// all unique triples summing to 0 (sort + two pointers)
function threeSum(nums) {
nums.sort((a, b) => a - b); // numeric sort; default lexicographic ভুল দিত
const n = nums.length, res = [];
for (let i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // একই fixed element নয়
if (nums[i] > 0) break; // সবচেয়ে ছোটটাই positive -> আর 0 নয়
let left = i + 1, right = n - 1;
while (left < right) {
const total = nums[i] + nums[left] + nums[right];
if (total < 0) left++;
else if (total > 0) right--;
else {
res.push([nums[i], nums[left], nums[right]]);
left++; right--;
while (left < right && nums[left] === nums[left - 1]) left++; // dup skip
while (left < right && nums[right] === nums[right + 1]) right--;
}
}
}
return res;
}
// ---- test cases (example + edge) ----
assert(eq(threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]]), "classic");
assert(eq(threeSum([0, 1, 1]), []), "none");
assert(eq(threeSum([0, 0, 0]), [[0, 0, 0]]), "all-zero"); // edge
assert(eq(threeSum([0, 0, 0, 0]), [[0, 0, 0]]), "dup-zero"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** `nums.sort()` default-এ string-এর মতো sort করে (`10 < 9`), তাই সংখ্যার জন্য সবসময় `(a, b) => a - b` comparator দাও — এটাই এই problem-এ সবচেয়ে common bug। nested array compare-এ `JSON.stringify`।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const res: number[][] = [];
for (let i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
if (nums[i] > 0) break;
let left = i + 1, right = n - 1;
while (left < right) {
const total: number = nums[i] + nums[left] + nums[right];
if (total < 0) left++;
else if (total > 0) right--;
else {
res.push([nums[i], nums[left], nums[right]]);
left++; right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
}
}
}
return res;
}
function expectArr(actual: number[][], exp: number[][], msg = ""): void {
if (JSON.stringify(actual) !== JSON.stringify(exp))
throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]], "classic");
expectArr(threeSum([0, 0, 0, 0]), [[0, 0, 0]], "dup-zero");
console.log("সব TS test pass!");
```
> **TS টীকা:** return type `number[][]` declare করায় ভুল করে flat `number[]` বা mixed array push করলে compiler আটকায়; triple-এর গঠন টাইপেই নথিভুক্ত থাকে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n^2)** — sort O(n log n), তারপর প্রতিটা fixed element-এ two-pointer scan O(n), মোট O(n^2) যা sort-কে ছাপিয়ে যায়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1) extra** (output বাদে) — দুই pointer আর কয়েকটা scalar; sort in place ধরে নিলে result list ছাড়া বাড়তি memory নগণ্য।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- duplicate skip বাদ দেওয়া — তখন একই triple বারবার আসে।
- fixed element-এর duplicate (`nums[i] == nums[i-1]`) skip ভুলে যাওয়া — প্রথম স্তরেই repeat।
- triple পাওয়ার পর শুধু `left++` বা শুধু `right--` করা — দুটোই সরাতে হয়, নইলে আবার একই sum-এ আটকাও।
- sort না করে two-pointer চালানো — sorted order ছাড়া pointer-movement যুক্তি ভেঙে পড়ে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Two Sum (#2)-এর pair-finding, একটা element fix করে। sorted two-pointer অংশটা Two Sum II আর Container With Most Water (#12)-এর discard যুক্তির ভাই। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 1 — Two Pointers" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Two Sum (ভিত্তি pair-sum) —