Problem link ও উৎস
- **Original source:** Classic pair-sum complement exercise
- **Platform:** LeetCode —
- **Topic:** hash map (Counter)
- **Difficulty:** Medium
- **Pattern:** complement lookup (pair sums)
- **Basic idea inherited from:** Two Sum — দুটো array-কে এক "pair" ধরে complement খোঁজা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
চারটা সমান-দৈর্ঘ্যের array `A`, `B`, `C`, `D` দেওয়া আছে। গুনতে হবে কতগুলো চতুষ্টয় index `(i, j, k, l)` আছে যাদের জন্য `A[i] + B[j] + C[k] + D[l] == 0`। অর্থাৎ প্রতিটা array থেকে একটা করে সংখ্যা নিয়ে যোগফল শূন্য হওয়ার মোট কতগুলো উপায়।
```text
A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]
যেমন A[0]+B[1]+C[0]+D[1] = 1+(-1)+(-1)+2 = 1 ... (এটা নয়)
মোট শূন্য-যোগফল চতুষ্টয়: 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2] Output: 2
Input : A=[0], B=[0], C=[0], D=[0] Output: 1
Input : A=[0,0], B=[0,0], C=[0,0], D=[0,0] Output: 16
Input : A=[1], B=[2], C=[3], D=[4] Output: 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুটো দল মিলে দাঁড়িপাল্লা শূন্যে আনতে চায়। বাম পাল্লার সব সম্ভাব্য ওজন-সংমিশ্রণ তুমি আগে একটা খাতায় গুনে রাখলে ("এই মোট ওজন এতবার বানানো যায়")। এবার ডান পাল্লার প্রতিটা সংমিশ্রণের জন্য শুধু দেখো — "এর ঠিক উল্টো ওজন বাম খাতায় কতবার আছে?" প্রতিটা ম্যাচ একটা ভারসাম্যের উপায়। সব জোড়া-জোড়া মেলানোর দরকার নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Two Sum** (#1)-এর complement lookup-এর একটা চমৎকার সম্প্রসারণ। Two Sum-এ একটা সংখ্যার partner খুঁজতাম; এখানে দুটো array-কে একসাথে একটা "বাম জোড়া" (A+B) আর বাকি দুটোকে "ডান জোড়া" (C+D) ধরে, এক জোড়ার যোগফলের জন্য অন্য জোড়ায় complement খুঁজি। [../patterns.md](../patterns.md)-তে এটা Pattern 2-এর "দ্বিগুণ করা" রূপ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো বীজগণিত: `A[i] + B[j] + C[k] + D[l] = 0` কে দুই ভাগে ভাঙো — `(A[i] + B[j]) + (C[k] + D[l]) = 0`, অর্থাৎ `A[i] + B[j] = -(C[k] + D[l])`। তাই বাম জোড়ার সব সম্ভাব্য যোগফল আগে গুনে রাখলে, ডান জোড়ার প্রতিটা যোগফল `s`-এর জন্য আমরা শুধু জিজ্ঞেস করি "বাম জোড়ায় `-s` কতবার এসেছে?" — চারটা loop-কে দুটো জোড়া-loop-এ নামিয়ে আনা।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map / Counter** (`pair-sum → কতবার`)। প্রথমে `A` ও `B`-র সব জোড়ার যোগফল গুনে Counter-এ রাখি। তারপর `C` ও `D`-র জোড়ায় হেঁটে complement-এর count যোগ করি। Counter সুবিধাজনক কারণ অনুপস্থিত key-তে এটা 0 ফেরত দেয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমরা **গুনছি** (কোনো একটা জোড়া খুঁজছি না), তাই value হিসেবে count দরকার — Counter ঠিক তাই দেয়। আর "complement pair-sum কতবার এসেছে?" — এই lookup গড়ে O(1)। ফলে চারটা nested loop-এর O(n^4) নেমে আসে O(n^2)-এ: একটা O(n^2) বাম জোড়া গোনায়, আরেকটা O(n^2) ডান জোড়ায় lookup-এ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: চারটা nested loop ধরে প্রতিটা চতুষ্টয় `(i, j, k, l)` পরীক্ষা করো।
```text
count = 0
প্রতিটা i, j, k, l-র জন্য:
A[i] + B[j] + C[k] + D[l] == 0 হলে count += 1
return count
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
চারটা nested loop মানে **O(n^4)** — n একটু বড় হলেই (যেমন 200) এটা কোটি কোটি অপারেশন। অপচয়টা Two Sum-এর মতোই: ডান জোড়ার প্রতিটা যোগফলের জন্য আমরা পুরো বাম দিক নতুন করে scan করছি, যদিও বাম জোড়ার যোগফলগুলো একবার গুনে রাখলেই complement instant পাওয়া যেত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **চার-যোগফলকে দুটো জোড়া-যোগফলে ভাগ করা যায়**, আর তখন এটা Two Sum। `A[i]+B[j]` কে এক একক হিসেবে গুনে রাখলে, `C[k]+D[l]`-এর জন্য partner ঠিক `-(C[k]+D[l])` — হিসেব করা যায়, খুঁজে বেড়াতে হয় না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথম দুটো array-র সব জোড়ার যোগফল `Counter`-এ গুনে রাখো (O(n^2))। তারপর শেষ দুটো array-র প্রতিটা জোড়ায় হেঁটে `count += ab[-(c + d)]` যোগ করো (O(n^2))। প্রতিটা পুরোনো ম্যাচই একটা বৈধ চতুষ্টয়। মোট **O(n^2)** time।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *বড় সংখ্যক জিনিসকে দুই অর্ধে ভাগ করো (meet in the middle); এক অর্ধের যোগফল গুনে রাখো, অন্য অর্ধে complement খোঁজো।* Two Sum-এর "search না করে remember করো" এখানে জোড়ার স্তরে কাজ করছে — তাই O(n^4) → O(n^2)।
### ছবিতে বোঝা {#7-visual-explanation}
`A=[1,2]`, `B=[-2,-1]`, `C=[-1,2]`, `D=[0,2]`। আগে A+B গুনি, পরে C+D-তে complement খুঁজি:
```text
ab (A[i]+B[j] → count):
1+(-2)=-1, 1+(-1)=0, 2+(-2)=0, 2+(-1)=1 → {-1:1, 0:2, 1:1}
cd জোড়া, প্রতিটায় need = -(C+D):
-1+0 = -1 → need 1 → ab[1]=1 → count 1
-1+2 = 1 → need -1 → ab[-1]=1 → count 2
2+0 = 2 → need -2 → ab[-2]=0 → count 2
2+2 = 4 → need -4 → ab[-4]=0 → count 2
উত্তর: 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `A=[0]`, `B=[0]`, `C=[0]`, `D=[0]`:
1. বাম জোড়া: `A[0]+B[0] = 0` → `ab = {0: 1}`।
2. ডান জোড়া: `C[0]+D[0] = 0`; need `-(0) = 0`; `ab[0] = 1` → `count = 1`।
3. উত্তর: `1` — একমাত্র চতুষ্টয় `(0,0,0,0)`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import Counter
def four_sum_count(A, B, C, D):
ab = Counter() # (a+b) -> কতবার
for a in A:
for b in B:
ab[a + b] += 1
count = 0
for c in C:
for d in D:
count += ab[-(c + d)] # complement pair-sum খুঁজি
return count
# ---- tests ----
assert four_sum_count([1, 2], [-2, -1], [-1, 2], [0, 2]) == 2
assert four_sum_count([0], [0], [0], [0]) == 1
assert four_sum_count([0, 0], [0, 0], [0, 0], [0, 0]) == 16
assert four_sum_count([1], [2], [3], [4]) == 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `ab = Counter()` — বাম জোড়ার যোগফলের গণনা; অনুপস্থিত key-তে 0 দেয়।
- `for a in A: for b in B: ab[a + b] += 1` — `A` ও `B`-র প্রতিটা জোড়ার যোগফল গুনে রাখি (O(n^2))।
- `count = 0` — মোট বৈধ চতুষ্টয়।
- `for c in C: for d in D` — `C` ও `D`-র প্রতিটা জোড়ায় হাঁটি।
- `count += ab[-(c + d)]` — এই জোড়ার complement বাম দিকে যতবার আছে, ততগুলো চতুষ্টয় যোগ হলো।
- `return count` — সব মিলিয়ে উত্তর।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]`-এ `ab = {-1:1, 0:2, 1:1}`; C+D জোড়াগুলোর মধ্যে `-1+0=-1` (need 1, পায় 1) আর `-1+2=1` (need -1, পায় 1) মেলে → count 2। চার আলাদা সংখ্যা `[1],[2],[3],[4]`-এ যোগফল কখনো 0 হয় না → 0। সব-শূন্য 2×2 case-এ `ab={0:4}`, চারটা C+D জোড়া প্রতিটা 4 করে গোনে → 16। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n^2)** — বাম জোড়া গোনা O(n^2), ডান জোড়ায় lookup O(n^2)। নাইভ O(n^4)-এর তুলনায় বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n^2)** — worst case-এ বাম জোড়ার সব আলাদা যোগফল Counter-এ জমতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- count নয়, existence (set) রাখা — তাহলে একই যোগফল একাধিকবার বানানোর উপায়গুলো গোনা বাদ পড়বে; **Counter** লাগবে।
- ভাগটা ভুল করা — সব O(n^2) জোড়াকে দুই অর্ধে (A+B বনাম C+D) ভাগ করতে হবে; তিন-এক ভাগ করলে সুবিধা যায় না।
- complement-এ ঋণচিহ্ন ভুলে যাওয়া — দরকার `-(c + d)`, কারণ চার যোগফল 0 চাই; `c + d` খুঁজলে ভুল উত্তর।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Two Sum (#1)-এর complement lookup, এখানে জোড়ার স্তরে তোলা ("meet in the middle")। এই note দেখায় কীভাবে একই tweak বড় মাত্রার (4-variable) problem-কেও সামলায়। সম্পূর্ণ চাল [../patterns.md](../patterns.md)-র Pattern 2-এ (4Sum II উদাহরণসহ উল্লেখিত)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Two Sum —