Problem link ও উৎস
- **Original source:** LeetCode 3Sum
- **Platform:** LeetCode —
- **Topic:** Two pointers → fix one element + opposite-pointer scan
- **Difficulty:** Medium
- **Pattern:** fix + two pointers (একজনকে বসিয়ে বাকি দুজনে opposite খোঁজ)
- **Basic idea inherited from:** 081 — Two Sum Sorted (fix করার পর বাকিটা ঠিক 081)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array দেওয়া। খুঁজতে হবে এমন সব **distinct triple** `[a, b, c]` যাদের `a + b + c == 0`। একই triple দুবার থাকা যাবে না (মান অনুসারে unique)। উত্তর হলো triple-গুলোর একটা list।
মূল ঝামেলা দুটো: (১) O(n³)-কে নামানো, (২) duplicate triple এড়ানো — কারণ একই তিন মান নানা index থেকে বারবার আসতে পারে।
### Input ও output {#6-example-input-and-output}
```text
a -> triples (a+b+c==0)
-------------------------------------------------
[-1, 0, 1, 2, -1, -4] -> [[-1, -1, 2], [-1, 0, 1]]
[0, 0, 0] -> [[0, 0, 0]]
[0, 1, 1] -> [] (যোগফল 0 হয় না)
[] -> []
[-2, 0, 0, 2, 2] -> [[-2, 0, 2]]
[-1, -1, -1, 2] -> [[-1, -1, 2]] (একবারই, duplicate skip)
```
Edge case: খালি বা 3-এর কম element → `[]`; একই triple নানা index থেকে এলেও একবারই।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে একগাদা তাপমাত্রার রিডিং (কিছু +, কিছু −), আর তুমি এমন তিনটা রিডিং চাও যাদের যোগফল ঠিক 0 (একে অন্যকে কাটাকাটি করে ফেলে)।
কৌশল: একটা রিডিং হাতে নিয়ে বসো (ধরো +5)। এখন বাকিদের মধ্যে এমন দুটো খোঁজো যাদের যোগফল −5। বাকিদের সাজিয়ে নিলে (sorted) দুই প্রান্ত থেকে চাপা দিয়ে সহজেই −5-এর জুটি পাও। তারপর হাতের রিডিং বদলে আবার একই খোঁজ। "একজনকে বসিয়ে বাকিদের চেনা খেলা" — এটাই মূল চাল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **081 — Two Sum Sorted**-এর কাঁধে। 083-এর ভেতরের লুপটা হুবহু 081 — শুধু target এখন `-a[i]`, আর আমরা সব জুটি (একটা না) চাই।
বাড়তি যা শিখছ: **duplicate handling**। 081-এ ঠিক একটা উত্তর ছিল, তাই duplicate ভাবতে হয়নি। এখানে সব unique triple চাই, তাই:
- **fix-এ skip**: `a[i]` আগেরটার সমান হলে continue (একই fix আবার করলে একই triple)
- **pointer-এ skip**: match পাওয়ার পর `l`, `r`-কে duplicate মান পেরিয়ে নেওয়া
081 + এই duplicate-শৃঙ্খলা = 083।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **সমস্যাকে এক ধাপ কমিয়ে চেনা সমস্যায় নামানো (reduction)**। `a + b + c == 0` মানে, `a`-কে fix করলে বাকিটা দাঁড়ায় `b + c == -a` — যা ঠিক **two-sum** (081)! তিন-মাত্রার খোঁজ এক fix করে দুই-মাত্রায় নেমে এল, আর দুই-মাত্রা sorted-এ O(n)। তাই মোট O(n²)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — তিনটা nested loop, আর duplicate এড়াতে sorted-tuple set:
```python
def three_sum_brute(a):
n = len(a)
found = set()
for i in range(n):
for j in range(i + 1, n):
for kk in range(j + 1, n):
if a[i] + a[j] + a[kk] == 0:
found.add(tuple(sorted((a[i], a[j], a[kk]))))
return [list(t) for t in sorted(found)]
```
ঠিক উত্তর দেয়, কিন্তু তিন স্তরের loop।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
তিনটা nested loop মানে প্রায় n³/6 triple। n = 3000 হলে প্রায় ৪৫০ কোটি — Time Limit Exceeded।
```text
n = 3000 হলে:
brute force : ~4,500,000,000 triple (O(n³))
fix + 2ptr : ~9,000,000 step (O(n²), অনেক দ্রুত)
```
মূল অপচয়: ভেতরের দুটো loop আসলে "একটা জুটি খোঁজা" — যেটা sorted-এ O(n²) না, O(n) দিয়েই হয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **sort করে নাও, একটা `a[i]` fix করো, বাকিটা 081-এর two-sum (target = `-a[i]`)।**
```text
for i in range(n-2):
fix a[i]; target = -a[i]
l, r = i+1, n-1
while l < r:
s = a[l] + a[r]
s == target → triple পেলে, l++ r-- (duplicate skip সহ)
s < target → l++ (যোগ বাড়াও)
s > target → r-- (যোগ কমাও)
```
duplicate এড়াতে: fix-এ `a[i] == a[i-1]` হলে skip, আর match-এর পরে `l`/`r`-কে সমান-মান পেরিয়ে নেওয়া।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **তিনটা সংখ্যার খোঁজ আসলে "একটা fix + একটা জুটি" — আর জুটি খোঁজা তো আগেই শিখেছি।** কঠিন সমস্যাকে চেনা সহজ সমস্যায় নামানোই (reduction) এখানকার বড় চাল।
আর duplicate skip-এর দুটো জায়গা — fix-এ একবার, pointer-এ একবার — না থাকলে `[-1,-1,2]` বারবার আসবে। এই দুই skip-ই unique-এর গ্যারান্টি।
### ছবিতে বোঝা {#5-visual-explanation}
`a` sort করার পর `a[i]` fix, ভেতরে `l`/`r` দুই প্রান্ত থেকে `-a[i]` খোঁজে:
```text
sorted a = [ -4 , -1 , -1 , 0 , 1 , 2 ]
i l r
i fix করল -4 → বাকিদের মধ্যে যোগফল +4 চাই
l=-1, r=2 : -1+2 = 1 < 4 → l++ ... (এখানে 4 মেলে না, i এগোবে)
i = -1 (index 1): বাকিদের যোগফল +1 চাই
l(index2)=-1, r=2 : -1+2 = 1 ✓ → triple [-1, -1, 2]
তারপর l++, r-- করে আরো খুঁজি → l=0, r=1 : 0+1 = 1 ✓ → triple [-1, 0, 1]
```
প্রতিটা fix-এর ভেতরে ঠিক 081-এর ছবি: দুই আঙুল ভেতরে এসে target ধরছে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [-1, 0, 1, 2, -1, -4]`। sort → `[-4, -1, -1, 0, 1, 2]`। ছোট করে দুটো fix দেখি:
| i (fix) | a[i] | target | l, r শুরু | যা ঘটে |
| --- | --- | --- | --- | --- |
| 0 | -4 | 4 | l=1, r=5 | কোনো জুটি 4 মেলে না (max -1+2=1) |
| 1 | -1 | 1 | l=2, r=5 | a[2]+a[5] = -1+2 = 1 ✓ → triple [-1,-1,2]; l++ r-- |
| | | | l=3, r=4 | a[3]+a[4] = 0+1 = 1 ✓ → triple [-1,0,1]; l++ r-- → l>r থামে |
| 2 | -1 | — | — | a[2]==a[1] → fix skip (একই triple এড়ালাম) |
| 3 | 0 | 0 | l=4, r=5 | 1+2 = 3 > 0 → r-- → l==r থামে |
ফল: `[[-1, -1, 2], [-1, 0, 1]]`। লক্ষ করো i=2-তে fix skip না করলে `[-1,-1,2]` আবার আসত।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def three_sum(a):
"""a+b+c==0 এমন সব distinct triple-এর list ফেরত দেয়।"""
a = sorted(a)
n = len(a)
res = []
for i in range(n - 2):
if a[i] > 0:
break # sorted-এ a[i]>0 হলে তিনজনই ধনাত্মক, যোগফল 0 অসম্ভব
if i > 0 and a[i] == a[i - 1]:
continue # একই fix আবার করলে একই triple
l, r = i + 1, n - 1
target = -a[i]
while l < r:
s = a[l] + a[r]
if s == target:
res.append([a[i], a[l], a[r]])
l += 1
r -= 1
while l < r and a[l] == a[l - 1]:
l += 1 # বাঁ দিকের duplicate পার হও
while l < r and a[r] == a[r + 1]:
r -= 1 # ডান দিকের duplicate পার হও
elif s < target:
l += 1
else:
r -= 1
return res
def three_sum_brute(a):
"""ধীর reference — তিন nested loop + set দিয়ে unique triple।"""
n = len(a)
found = set()
for i in range(n):
for j in range(i + 1, n):
for kk in range(j + 1, n):
if a[i] + a[j] + a[kk] == 0:
found.add(tuple(sorted((a[i], a[j], a[kk]))))
return [list(t) for t in sorted(found)]
def _norm(triples):
"""তুলনার জন্য triple-গুলোকে এক ক্রমে সাজাই।"""
return sorted(tuple(sorted(t)) for t in triples)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert _norm(three_sum([-1, 0, 1, 2, -1, -4])) == _norm([[-1, -1, 2], [-1, 0, 1]])
assert _norm(three_sum([0, 0, 0])) == _norm([[0, 0, 0]])
assert three_sum([0, 1, 1]) == []
assert three_sum([]) == []
assert _norm(three_sum([-2, 0, 0, 2, 2])) == _norm([[-2, 0, 2]])
assert _norm(three_sum([-1, -1, -1, 2])) == _norm([[-1, -1, 2]])
# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(11)
for _ in range(300):
arr = [random.randint(-4, 4) for _ in range(random.randint(0, 8))]
assert _norm(three_sum(arr)) == _norm(three_sum_brute(arr)), arr
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 0, 0])) # [[0, 0, 0]]
print(three_sum([0, 1, 1])) # []
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
a = sorted(a)
```
sort না করলে opposite pointers আর duplicate-skip কিছুই খাটে না — প্রথম ও আবশ্যক ধাপ।
```text
if a[i] > 0: break
```
ছোট optimization — sorted-এ fix-ই ধনাত্মক হলে বাকি দুজনও ধনাত্মক, যোগফল কখনো 0 হবে না।
```text
if i > 0 and a[i] == a[i-1]: continue
```
fix-level duplicate skip — একই মান আবার fix করলে একই triple আসবে।
```text
l, r = i + 1, n - 1 ; target = -a[i]
while l < r: s = a[l] + a[r]
```
ঠিক 081 — fix-এর ডান পাশে দুই প্রান্ত থেকে `-a[i]` খোঁজা।
```text
if s == target: res.append(...); l++; r--
while a[l]==a[l-1]: l++ ; while a[r]==a[r+1]: r--
```
match পেলে triple জমাও, তারপর দুই দিকেই duplicate মান পেরিয়ে যাও (pointer-level skip)।
```text
elif s < target: l++ else: r--
```
যোগফল কম হলে বাঁ বাড়াও, বেশি হলে ডান কমাও — 081-এর সেই নিয়ম।
`three_sum_brute` ও `_norm` শুধু test যাচাইয়ের জন্য; random case-এ দুই পথ মিলিয়ে দেখা হয়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[[-1, -1, 2], [-1, 0, 1]]
[[0, 0, 0]]
[]
সব test pass!
```
প্রথম লাইন দুটো triple; দ্বিতীয় লাইন `[0,0,0]`; তৃতীয় লাইন খালি (যোগফল 0 হয় না)। তার আগে 300 random case brute-force-এর সাথে মিলেছে, তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n²)** — sort O(n log n), তারপর বাইরের fix-loop O(n) × ভেতরের two-pointer O(n) = O(n²)। n²-ই প্রধান, তাই মোট O(n²)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** extra (output বাদে) — `l`, `r`, `target` ছাড়া কিছু না (in-place sort ধরলে)। Output list-টা ফলাফল ধরে, তাই সেটা গোনার বাইরে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **fix-level duplicate skip ভুলে যাওয়া** — `a[i]==a[i-1]` skip না করলে একই triple বারবার।
- **pointer-level duplicate skip ভুলে যাওয়া** — match-এর পরে `l`/`r`-কে সমান-মান না পেরোলে `[-1,-1,2]` দুবার।
- **`l <= r` লেখা** — `l < r` না হলে একই element দুবার ব্যবহার বা ভুল।
- **Sort না করা** — তাহলে পুরো two-pointer যুক্তি ভেঙে পড়ে।
- **match-এর পর শুধু `l++` করা, `r--` না** — একটা triple পেলে দুই দিকই সরাতে হয়, নাহলে অসীম বা ভুল।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode 3Sum** (