083 — Three Sum¶
081-এ শিখেছ দুটো সংখ্যার জুটি খুঁজতে opposite pointers। এখানে প্রশ্নটা একধাপ উপরে — তিনটা সংখ্যা যাদের যোগফল 0। সরল ভাবলে তিনটা nested loop, O(n³)। কিন্তু একটা সুন্দর কৌশল আছে: একজনকে বসিয়ে রেখে বাকি দুজনে 081-এর খেলাই খেলা। সাথে duplicate এড়ানোর কড়া অনুশীলন — interview-তে এখানেই বেশি মানুষ আটকায়। ধীরে পড়ো।
Source¶
- Original source: LeetCode 3Sum
- Platform: LeetCode — https://leetcode.com/problems/3sum/
- 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)
1. Problem in simple words¶
একটা array দেওয়া। খুঁজতে হবে এমন সব distinct triple [a, b, c] যাদের a + b + c == 0। একই triple দুবার থাকা যাবে না (মান অনুসারে unique)। উত্তর হলো triple-গুলোর একটা list।
মূল ঝামেলা দুটো: (১) O(n³)-কে নামানো, (২) duplicate triple এড়ানো — কারণ একই তিন মান নানা index থেকে বারবার আসতে পারে।
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²)।
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।
4. Real-life analogy¶
ভাবো তোমার কাছে একগাদা তাপমাত্রার রিডিং (কিছু +, কিছু −), আর তুমি এমন তিনটা রিডিং চাও যাদের যোগফল ঠিক 0 (একে অন্যকে কাটাকাটি করে ফেলে)।
কৌশল: একটা রিডিং হাতে নিয়ে বসো (ধরো +5)। এখন বাকিদের মধ্যে এমন দুটো খোঁজো যাদের যোগফল −5। বাকিদের সাজিয়ে নিলে (sorted) দুই প্রান্ত থেকে চাপা দিয়ে সহজেই −5-এর জুটি পাও। তারপর হাতের রিডিং বদলে আবার একই খোঁজ। "একজনকে বসিয়ে বাকিদের চেনা খেলা" — এটাই মূল চাল।
5. Visual explanation¶
a sort করার পর a[i] fix, ভেতরে l/r দুই প্রান্ত থেকে -a[i] খোঁজে:
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 ধরছে।
6. Example input and output¶
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 থেকে এলেও একবারই।
7. Brute force thinking¶
সরল পথ — তিনটা nested loop, আর duplicate এড়াতে sorted-tuple set:
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।
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])।
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-এর গ্যারান্টি।
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] আবার আসত।
12. Python solution¶
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¶
sort না করলে opposite pointers আর duplicate-skip কিছুই খাটে না — প্রথম ও আবশ্যক ধাপ।
ছোট optimization — sorted-এ fix-ই ধনাত্মক হলে বাকি দুজনও ধনাত্মক, যোগফল কখনো 0 হবে না।
fix-level duplicate skip — একই মান আবার fix করলে একই triple আসবে।
ঠিক 081 — fix-এর ডান পাশে দুই প্রান্ত থেকে -a[i] খোঁজা।
match পেলে triple জমাও, তারপর দুই দিকেই duplicate মান পেরিয়ে যাও (pointer-level skip)।
যোগফল কম হলে বাঁ বাড়াও, বেশি হলে ডান কমাও — 081-এর সেই নিয়ম।
three_sum_brute ও _norm শুধু test যাচাইয়ের জন্য; random case-এ দুই পথ মিলিয়ে দেখা হয়।
14. Output walkthrough¶
চালালে ছাপবে:
প্রথম লাইন দুটো triple; দ্বিতীয় লাইন [0,0,0]; তৃতীয় লাইন খালি (যোগফল 0 হয় না)। তার আগে 300 random case brute-force-এর সাথে মিলেছে, তাই সব test pass!।
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 পেলে দুই দিকই সরাতে হয়, নাহলে অসীম বা ভুল।
18. Harder problems that inherit this idea¶
- LeetCode 3Sum (https://leetcode.com/problems/3sum/) — এই problem-এরই মূল রূপ।
- LeetCode 3Sum Closest (https://leetcode.com/problems/3sum-closest/) — একই fix + 2ptr, তবে target-এর সবচেয়ে কাছের যোগফল।
- LeetCode 4Sum (https://leetcode.com/problems/4sum/) — দুটো fix + 2ptr, একই reduction আরো এক ধাপ।
19. Pattern learned¶
Fix one + two pointers (problem reduction) — sort, একটা element fix, বাকিটা two-sum; duplicate দুই স্তরে skip। বড় শিক্ষা: k-Sum মানে এক element fix করে (k−1)-Sum — কঠিনকে চেনা সহজে নামানোই আসল চাল।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "3Sum = sort + একটা fix + ভেতরে 081-এর two-sum (target −a[i]); duplicate fix-এ ও pointer-এ — দুই জায়গায় skip। Signal: 'k সংখ্যার যোগফল = target' দেখলে এক fix + (k−1)Sum মাথায় আসুক।"
পরের ধাপ → 084 — Container With Most Water (আবার দুই প্রান্ত, তবে move-এর পেছনে প্রমাণ)। ভিত্তি → 081 — Two Sum Sorted।
ফিরে দেখা: এই 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" লেখো।