016 — 4Sum II¶

Source¶

Original source: Classic pair-sum complement exercise
Platform: LeetCode — https://leetcode.com/problems/4sum-ii/
Topic: hash map (Counter)
Difficulty: Medium
Pattern: complement lookup (pair sums)
Basic idea inherited from: Two Sum — দুটো array-কে এক "pair" ধরে complement খোঁজা

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 থেকে একটা করে সংখ্যা নিয়ে যোগফল শূন্য হওয়ার মোট কতগুলো উপায়।

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

2. Which basic idea does this inherit from?¶

এটা Two Sum (#1)-এর complement lookup-এর একটা চমৎকার সম্প্রসারণ। Two Sum-এ একটা সংখ্যার partner খুঁজতাম; এখানে দুটো array-কে একসাথে একটা "বাম জোড়া" (A+B) আর বাকি দুটোকে "ডান জোড়া" (C+D) ধরে, এক জোড়ার যোগফলের জন্য অন্য জোড়ায় complement খুঁজি। ../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-এ।

6. Real-life analogy¶

ভাবো দুটো দল মিলে দাঁড়িপাল্লা শূন্যে আনতে চায়। বাম পাল্লার সব সম্ভাব্য ওজন-সংমিশ্রণ তুমি আগে একটা খাতায় গুনে রাখলে ("এই মোট ওজন এতবার বানানো যায়")। এবার ডান পাল্লার প্রতিটা সংমিশ্রণের জন্য শুধু দেখো — "এর ঠিক উল্টো ওজন বাম খাতায় কতবার আছে?" প্রতিটা ম্যাচ একটা ভারসাম্যের উপায়। সব জোড়া-জোড়া মেলানোর দরকার নেই।

7. Visual explanation¶

A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]। আগে A+B গুনি, পরে C+D-তে complement খুঁজি:

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

8. Example input and output¶

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: চারটা nested loop ধরে প্রতিটা চতুষ্টয় (i, j, k, l) পরীক্ষা করো।

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)।

14. Step-by-step dry run¶

Input A=[0], B=[0], C=[0], D=[0]:

বাম জোড়া: A[0]+B[0] = 0 → ab = {0: 1}।
ডান জোড়া: C[0]+D[0] = 0; need -(0) = 0; ab[0] = 1 → count = 1।
উত্তর: 1 — একমাত্র চতুষ্টয় (0,0,0,0)।

15. Python solution¶

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 — সব মিলিয়ে উত্তর।

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!।

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 খুঁজলে ভুল উত্তর।

21. Which basic problem this inherits from¶

ভিত্তি: Two Sum (#1)-এর complement lookup, এখানে জোড়ার স্তরে তোলা ("meet in the middle")। এই note দেখায় কীভাবে একই tweak বড় মাত্রার (4-variable) problem-কেও সামলায়। সম্পূর্ণ চাল ../patterns.md-র Pattern 2-এ (4Sum II উদাহরণসহ উল্লেখিত)।

22. Similar harder problems¶

Two Sum — https://leetcode.com/problems/two-sum/ (এই tracker-এর #1; complement-এর মূল রূপ)
4Sum — https://leetcode.com/problems/4sum/ (একই array, distinct চতুষ্টয় — sort + two pointers)
3Sum — https://leetcode.com/problems/3sum/ (তিন-যোগফল, sort + two pointers)

23. Pattern learned¶

Complement lookup on pair sums (meet in the middle): চার-যোগফলকে দুটো জোড়া-যোগফলে ভাগ করো; এক অর্ধের যোগফল Counter-এ গুনে রাখো, অন্য অর্ধের প্রতিটা যোগফলের complement (-s) কতবার আছে গোনো — O(n^4) থেকে O(n^2)।

24. Final summary¶

ভবিষ্যতের আমাকে: "চারটা (বা অনেক) array থেকে এক করে নিয়ে যোগফল target" শুনলেই দুই অর্ধে ভাগ করার কথা মনে পড়বে। মূল চাল — অর্ধেক জোড়ার যোগফল গুনে রাখো, বাকি অর্ধে complement খোঁজো। এটা Two Sum-এরই বড় সংস্করণ; tweak সেই একটাই — search না করে remember করো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।