016 — 3Sum

Problem link ও উৎস

• Original source: Classic sort + two-pointer exercise
• Platform: LeetCode — https://leetcode.com/problems/3sum/
• Topic: array / two pointers
• Difficulty: Medium
• Pattern: sort + two pointers (একটা element fix করে বাকি দুটো pair-sum)
• Basic idea inherited from: pair sum (problem 2) — একটা element fix করে, বাকি array-তে দুটোর যোগফল খোঁজা

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

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

একটা integer array nums দেওয়া। এমন সব unique triple (তিনটা ভিন্ন index) খুঁজে বের করো যাদের তিন value-র যোগফল ঠিক 0। উত্তরে একই triple দুবার থাকা যাবে না। triple-গুলোর list ফেরত দাও।

উদাহরণ

nums = [-1, 0, 1, 2, -1, -4]
0 হয় এমন triple: [-1, -1, 2] আর [-1, 0, 1]

Input ও output

উদাহরণ

Input : [-1, 0, 1, 2, -1, -4] -> [[-1, -1, 2], [-1, 0, 1]]
Input : [0, 1, 1]             -> []          (0 হয় এমন triple নেই)

Edge case 1 (সব শূন্য):       [0, 0, 0]    -> [[0, 0, 0]]
Edge case 2 (duplicate শূন্য): [0, 0, 0, 0] -> [[0, 0, 0]]   (একবারই)

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

ভাবো তিনজনের ওজন মিলে ঠিক শূন্য (ঋণ-ধন ভারসাম্য) চাই। একজনকে আগে বেছে নাও; এখন বাকিদের সারিতে দাঁড় করিয়ে (sorted) দুই প্রান্ত থেকে দুজনকে ধরো। তাদের যোগফল কম হলে বাঁয়ের জনকে ভারীজনে বদলাও, বেশি হলে ডানের জনকে হালকাজনে — মাঝে মিলে গেলে triple পেলে।

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

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

ভিত pair sum (Two Sum, problem 2)। একটা element nums[i] fix করলে বাকিটা হয়ে যায় "এমন দুটো সংখ্যা খুঁজি যাদের যোগফল -nums[i]" — অর্থাৎ একটা two-sum। array sort করে নিলে সেই two-sum-টা converging two pointers দিয়ে O(n)-এ করা যায়। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো।

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

লুকানো logic: a + b + c = 0 মানে একটা fix করলে b + c = -a। sorted array-তে দুই pointer (left, right)-এর sum target-এর চেয়ে ছোট হলে left ডানে (sum বাড়ে), বড় হলে right বাঁয়ে (sum কমে) — প্রতিটা move একটা candidate চিরতরে বাদ দেয়। duplicate এড়াতে sorted order কাজে লাগে: পাশাপাশি সমান value skip করলেই unique triple।

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

কোনো ভারী structure লাগে না — array-টা sort করি (O(n log n)), তারপর প্রতিটা fixed element-এ দুটো integer pointer। উত্তর জমাতে একটা result list। sort বাদে O(1) extra।

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

Sort করার পর array-র order-ই duplicate detection আর two-pointer movement দুটোকেই সম্ভব করে: সমান value পাশাপাশি আসে (skip সহজ), আর sum ছোট/বড় হলে কোন দিকে সরতে হবে তা নিশ্চিত। O(1) random access-এ দুই pointer-এর value সাথে সাথে পড়া যায়।

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

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

প্রথম সরল চিন্তা: তিনটা nested loop দিয়ে সব triple (i, j, l) try করো, যোগফল 0 হলে রাখো, আর শেষে duplicate বাদ দাও।

উদাহরণ

res = set()
for i in range(n):
    for j in range(i+1, n):
        for l in range(j+1, n):
            if nums[i] + nums[j] + nums[l] == 0:
                res.add(sorted triple)

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

তিনটা nested loop মানে O(n^3) — array একটু বড় হলেই অসম্ভব ধীর। উপরন্তু duplicate সামলাতে আলাদা set লাগে। sort + two-pointer দিয়ে এটা O(n^2)-এ নামে আর duplicate-ও sorted order থেকেই handle হয়।

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

মূল observation: একটা element fix করলে বাকিটা একটা two-sum (-nums[i] target)। sorted array-তে two-sum দুই pointer দিয়ে O(n); তাই মোট O(n^2)। আর sorted বলে পাশাপাশি সমান value skip করলেই unique triple — আলাদা dedup structure লাগে না।

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

array sort করো। প্রতিটা index i (fixed first element)-এ: যদি nums[i] == nums[i-1] হয় তবে skip (duplicate fixed); nums[i] > 0 হলে break (sorted-এ সবচেয়ে ছোটটাই positive মানে আর 0 হবে না)। তারপর left=i+1, right=n-1 নিয়ে two-pointer: sum 0-র চেয়ে ছোট → left++, বড় → right--, সমান → triple রাখো আর দুই pointer-এর duplicate skip করো। মোট O(n^2)।

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

মোচড়: "তিনটা loop ঘোরাব" (O(n^3)) ভুলে গিয়ে ভাবো "একটা fix করি, বাকিটা sorted two-sum।" তিন-যোগফলের সমস্যা ভেঙে যায় চেনা pair-sum-এ, আর sort duplicate-ও সামলে দেয়।

ছবিতে বোঝা

Sorted input [-4,-1,-1,0,1,2]। L/R হলো index; প্রতিটি সিদ্ধান্ত নিচে আছে।

fixed index/value	L,R	মোট	কাজ
0 / -4	1,5	-3	L=2
0 / -4	2,5	-3	L=3
0 / -4	3,5	-2	L=4
0 / -4	4,5	-1	L=5; এই fixed index শেষ
1 / -1	2,5	0	[-1,-1,2] record; L=3,R=4
1 / -1	3,4	0	[-1,0,1] record; L=4,R=3; শেষ
2 / -1	—	—	আগের fixed value-এর সমান: skip
3 / 0	4,5	3	R=4; শেষ

এর পরে তিনটি element বেছে নেওয়ার মতো suffix নেই। ফল [[−1,−1,2],[−1,0,1]]।

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

Input [0, 0, 0, 0] (sort করেও একই):

1. i=0 (nums[0]=0): left=1, right=3। sum 0+0+0=0 → triple [0,0,0] রাখি; left=2, right=2; দুই pointer-এর duplicate skip-এ left < right মিথ্যা → ভেতরের loop শেষ।
2. i=1 (nums[1]=0): nums[1] == nums[0] → duplicate fixed, continue।
3. i=2: range শেষ (range(n-2)=range(2) শুধু i=0,1)।
4. ফল: [[0, 0, 0]] (একবারই)।

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

Python

Python

def three_sum(nums):
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                       # একই fixed element আবার নয়
        if nums[i] > 0:
            break                          # সবচেয়ে ছোটটাই positive -> আর 0 হবে না
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1                  # sum বাড়াতে left ডানে
            elif total > 0:
                right -= 1                 # sum কমাতে right বাঁয়ে
            else:
                res.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1              # duplicate left skip
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1             # duplicate right skip
    return res

# ---- tests ----
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 1, 1]) == []
assert three_sum([0, 0, 0]) == [[0, 0, 0]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
print("সব test pass!")

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

• nums.sort() — duplicate skip আর two-pointer দুটোর জন্য sorted order জরুরি।
• for i in range(n - 2) — fixed first element; শেষ দুটো left/right-এর জন্য রাখা।
• if i > 0 and nums[i] == nums[i-1]: continue — একই value আবার fix করলে repeat triple আসত।
• if nums[i] > 0: break — sorted-এ এখান থেকে সব positive, তিন positive-এর যোগ কখনো 0 নয়।
• total = ... — fixed + দুই pointer-এর যোগফল।
• total < 0 → left += 1, total > 0 → right -= 1 — sorted বলে এই move গুলো sum-কে target-এর দিকে ঠেলে।
• else: triple রাখি, দুই pointer ভেতরে আনি, আর পাশের সমান value গুলো skip করে duplicate triple এড়াই।

Output মিলিয়ে দেখা

[-1,0,1,2,-1,-4] sort হয়ে [-4,-1,-1,0,1,2]; fix -1-এ [-1,-1,2] ও [-1,0,1], পরের -1 skip → [[-1,-1,2],[-1,0,1]], assert pass। [0,1,1] → কোনো 0-যোগ triple নেই, []; [0,0,0] ও [0,0,0,0] → দুটোতেই [[0,0,0]] একবার। শেষে print: সব test pass!।

JavaScript ও test cases

sort + two-pointer; JS-এ অবশ্যই numeric comparator (a,b)=>a-b লাগবে।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// all unique triples summing to 0 (sort + two pointers)
function threeSum(nums) {
  nums.sort((a, b) => a - b);          // numeric sort; default lexicographic ভুল দিত
  const n = nums.length, res = [];
  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;   // একই fixed element নয়
    if (nums[i] > 0) break;                            // সবচেয়ে ছোটটাই positive -> আর 0 নয়
    let left = i + 1, right = n - 1;
    while (left < right) {
      const total = nums[i] + nums[left] + nums[right];
      if (total < 0) left++;
      else if (total > 0) right--;
      else {
        res.push([nums[i], nums[left], nums[right]]);
        left++; right--;
        while (left < right && nums[left] === nums[left - 1]) left++;   // dup skip
        while (left < right && nums[right] === nums[right + 1]) right--;
      }
    }
  }
  return res;
}
// ---- test cases (example + edge) ----
assert(eq(threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]]), "classic");
assert(eq(threeSum([0, 1, 1]), []), "none");
assert(eq(threeSum([0, 0, 0]), [[0, 0, 0]]), "all-zero");                 // edge
assert(eq(threeSum([0, 0, 0, 0]), [[0, 0, 0]]), "dup-zero");              // edge
console.log("সব JS test pass!");

JS টীকা: nums.sort() default-এ string-এর মতো sort করে (10 < 9), তাই সংখ্যার জন্য সবসময় (a, b) => a - b comparator দাও — এটাই এই problem-এ সবচেয়ে common bug। nested array compare-এ JSON.stringify।

TypeScript ও test cases

TypeScript

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const res: number[][] = [];
  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    if (nums[i] > 0) break;
    let left = i + 1, right = n - 1;
    while (left < right) {
      const total: number = nums[i] + nums[left] + nums[right];
      if (total < 0) left++;
      else if (total > 0) right--;
      else {
        res.push([nums[i], nums[left], nums[right]]);
        left++; right--;
        while (left < right && nums[left] === nums[left - 1]) left++;
        while (left < right && nums[right] === nums[right + 1]) right--;
      }
    }
  }
  return res;
}
function expectArr(actual: number[][], exp: number[][], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp))
    throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]], "classic");
expectArr(threeSum([0, 0, 0, 0]), [[0, 0, 0]], "dup-zero");
console.log("সব TS test pass!");

TS টীকা: return type number[][] declare করায় ভুল করে flat number[] বা mixed array push করলে compiler আটকায়; triple-এর গঠন টাইপেই নথিভুক্ত থাকে।

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

সময়

O(n^2) — sort O(n log n), তারপর প্রতিটা fixed element-এ two-pointer scan O(n), মোট O(n^2) যা sort-কে ছাপিয়ে যায়।

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

O(1) extra (output বাদে) — দুই pointer আর কয়েকটা scalar; sort in place ধরে নিলে result list ছাড়া বাড়তি memory নগণ্য।

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

• duplicate skip বাদ দেওয়া — তখন একই triple বারবার আসে।
• fixed element-এর duplicate (nums[i] == nums[i-1]) skip ভুলে যাওয়া — প্রথম স্তরেই repeat।
• triple পাওয়ার পর শুধু left++ বা শুধু right-- করা — দুটোই সরাতে হয়, নইলে আবার একই sum-এ আটকাও।
• sort না করে two-pointer চালানো — sorted order ছাড়া pointer-movement যুক্তি ভেঙে পড়ে।

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

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

ভিত্তি: Two Sum (#2)-এর pair-finding, একটা element fix করে। sorted two-pointer অংশটা Two Sum II আর Container With Most Water (#12)-এর discard যুক্তির ভাই। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো।

পরের অনুশীলন

• Two Sum (ভিত্তি pair-sum) — https://leetcode.com/problems/two-sum/ (#2)
• 3Sum Closest (target-এর সবচেয়ে কাছের যোগফল) — https://leetcode.com/problems/3sum-closest/
• 4Sum (আরেক স্তর fix) — https://leetcode.com/problems/4sum/

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

Sort + two pointers (fix one, pair the rest): "zero-sum triple / k-sum" দেখলে array sort করো, একটা element fix করো, বাকিটা converging two-pointer pair-sum হিসেবে সমাধান করো — sorted order duplicate-ও সামলায়। O(n^2)।

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

ভবিষ্যতের আমাকে: "sort করো; একটা fix করো; বাকিটা -nums[i] target-এর two-sum; পাশের সমান value skip করো।" "sum 0 হওয়া triple / 3Sum" দেখলেই sort + two-pointer মনে করবে — O(n^2) time, O(1) extra।

কোথায় কাজে লাগে

• Financial reconciliation: তিনটা transaction মিলে নির্দিষ্ট target (যেমন net zero) হয় কিনা খোঁজা।
• Chemistry/physics balancing: তিনটা মান মিলে ভারসাম্য (যোগফল ধ্রুবক) এমন combination।
• Recommendation/bundling: তিনটা item মিলে নির্দিষ্ট budget/score ছোঁয় এমন bundle।
• Collision/geometry: তিন বিন্দুর coordinate-এর constraint যাচাই (sort + two-pointer base)।
• k-sum family: 4Sum, 3Sum Closest ইত্যাদি বড় সমস্যার ভিত্তি কৌশল।
• Sensor calibration: তিন offset মিলে শূন্য error দেয় এমন set খোঁজা।

মূল pattern: একটা fix করে বাকিটা sorted two-sum; sorted order duplicate-ও সামলায় — "zero-sum triple / k-sum" দেখলেই sort + two-pointer।

---

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