কনটেন্টে যান

016 — 4Sum II

Problem link ও উৎস

  • 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 খোঁজা

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

চারটা সমান-দৈর্ঘ্যের 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

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

লুকানো বীজগণিত: 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-এ নামিয়ে আনা।

কী দিয়ে তথ্য রাখব

একটা hash map / Counter (pair-sum → কতবার)। প্রথমে A ও B-র সব জোড়ার যোগফল গুনে Counter-এ রাখি। তারপর C ও D-র জোড়ায় হেঁটে complement-এর count যোগ করি। Counter সুবিধাজনক কারণ অনুপস্থিত key-তে এটা 0 ফেরত দেয়।

এটি কেন উপযুক্ত

আমরা গুনছি (কোনো একটা জোড়া খুঁজছি না), তাই value হিসেবে count দরকার — Counter ঠিক তাই দেয়। আর "complement pair-sum কতবার এসেছে?" — এই lookup গড়ে O(1)। ফলে চারটা nested loop-এর O(n^4) নেমে আসে O(n^2)-এ: একটা O(n^2) বাম জোড়া গোনায়, আরেকটা O(n^2) ডান জোড়ায় lookup-এ।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: চারটা 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

কোথায় বেশি কাজ হচ্ছে

চারটা nested loop মানে O(n^4) — n একটু বড় হলেই (যেমন 200) এটা কোটি কোটি অপারেশন। অপচয়টা Two Sum-এর মতোই: ডান জোড়ার প্রতিটা যোগফলের জন্য আমরা পুরো বাম দিক নতুন করে scan করছি, যদিও বাম জোড়ার যোগফলগুলো একবার গুনে রাখলেই complement instant পাওয়া যেত।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: চার-যোগফলকে দুটো জোড়া-যোগফলে ভাগ করা যায়, আর তখন এটা Two Sum। A[i]+B[j] কে এক একক হিসেবে গুনে রাখলে, C[k]+D[l]-এর জন্য partner ঠিক -(C[k]+D[l]) — হিসেব করা যায়, খুঁজে বেড়াতে হয় না।

আরও কম কাজে সমাধান

প্রথম দুটো array-র সব জোড়ার যোগফল Counter-এ গুনে রাখো (O(n^2))। তারপর শেষ দুটো array-র প্রতিটা জোড়ায় হেঁটে count += ab[-(c + d)] যোগ করো (O(n^2))। প্রতিটা পুরোনো ম্যাচই একটা বৈধ চতুষ্টয়। মোট O(n^2) time।

ভাবনার পরিবর্তন

মোচড়: বড় সংখ্যক জিনিসকে দুই অর্ধে ভাগ করো (meet in the middle); এক অর্ধের যোগফল গুনে রাখো, অন্য অর্ধে complement খোঁজো। Two Sum-এর "search না করে remember করো" এখানে জোড়ার স্তরে কাজ করছে — তাই O(n^4) → O(n^2)।

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

O(n^2) — বাম জোড়া গোনা O(n^2), ডান জোড়ায় lookup O(n^2)। নাইভ O(n^4)-এর তুলনায় বিশাল উন্নতি।

অতিরিক্ত জায়গা

O(n^2) — worst case-এ বাম জোড়ার সব আলাদা যোগফল Counter-এ জমতে পারে।

যে ভুলগুলো এড়াতে হবে

  • count নয়, existence (set) রাখা — তাহলে একই যোগফল একাধিকবার বানানোর উপায়গুলো গোনা বাদ পড়বে; Counter লাগবে।
  • ভাগটা ভুল করা — সব O(n^2) জোড়াকে দুই অর্ধে (A+B বনাম C+D) ভাগ করতে হবে; তিন-এক ভাগ করলে সুবিধা যায় না।
  • complement-এ ঋণচিহ্ন ভুলে যাওয়া — দরকার -(c + d), কারণ চার যোগফল 0 চাই; c + d খুঁজলে ভুল উত্তর।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

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