016 — 3Sum¶

Source¶

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-তে দুটোর যোগফল খোঁজা

1. Problem in simple words¶

একটা 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]

2. Which basic idea does this inherit from?¶

ভিত 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" দেখো।

3. What is the hidden math or logic?¶

লুকানো 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।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

nums = [-1, 0, 1, 2, -1, -4] → sort → [-4, -1, -1, 0, 1, 2]:

fix -4: L=-1 R=2 -> -4-1+2=-3<0 L++ ... কোনো জোড়া মেলে না
fix -1(i=1): L=-1 R=2 -> -1-1+2=0  -> [-1,-1,2]; L++ R--
             L= 0 R=1 -> -1+0+1=0  -> [-1,0,1]; শেষ
fix -1(i=2): আগেরটার সমান -> skip (duplicate)
fix  0: L=1 R=2 -> 0+1+2=3>0 R-- ... মেলে না
result: [[-1,-1,2], [-1,0,1]]

8. Example input and 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]]   (একবারই)

9. Brute force thinking¶

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

10. Why brute force is slow¶

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

11. Key observation¶

মূল 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 লাগে না।

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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 শেষ।
i=1 (nums[1]=0): nums[1] == nums[0] → duplicate fixed, continue।
i=2: range শেষ (range(n-2)=range(2) শুধু i=0,1)।
ফল: [[0, 0, 0]] (একবারই)।

15. Python solution¶

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

16. Line-by-line code explanation¶

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 এড়াই।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

ভিত্তি: 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" দেখো।

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

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

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।

26. TypeScript solution (with test cases)¶

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-এর গঠন টাইপেই নথিভুক্ত থাকে।

27. কোথায় কাজে লাগে (real-world use)¶

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।