Skip to content

002 — Two Sum

Source

  • Original source: Classic hash-map exercise
  • Platform: LeetCode — https://leetcode.com/problems/two-sum/
  • Topic: array / hash map
  • Difficulty: Easy
  • Pattern: frequency / complement lookup (hash map)
  • Basic idea inherited from: Math level 5 (prefix/contribution)-এর complement thinking — "যা দরকার সেটা আগে দেখেছি কিনা" খোঁজা

1. Problem in simple words

একটা integer array nums আর একটা target দেওয়া আছে। এমন দুটো index খুঁজে বের করো যাদের value যোগ করলে ঠিক target হয়। ধরে নাও ঠিক একটা উত্তর আছে, আর একই element দুবার ব্যবহার করা যাবে না। দুটো index ফেরত দাও।

nums = [2, 7, 11, 15], target = 9
2 + 7 = 9  ->  index 0 আর 1
উত্তর: [0, 1]

2. Which basic idea does this inherit from?

এটা math chapter-এর complement thinking reuse করে: প্রতিটা x-এর জন্য আমার দরকার তার "জোড়া" target - x। পুরো array জুড়ে সব pair না মিলিয়ে, প্রশ্নটা উল্টে দাও — "এই complement টা কি আগে কোথাও দেখেছি?" এই "আগে দেখেছি কিনা" idea-র গভীর রূপ ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/-তে (subarray sum K-এও একই trick)।

3. What is the hidden math or logic?

লুকানো logic: a + b = target সমীকরণটা একটা variable-এর হয়ে যায় — b = target - a। তাই প্রতিটা element-কে আলাদা করে অন্য সবার সাথে না মিলিয়ে, শুধু তার একমাত্র দরকারি জোড়া target - a খুঁজলেই হয়। আর সেই খোঁজা O(1)-এ করতে hash map।

4. Which data structure is needed?

একটা hash map (dict), যেখানে key = এ পর্যন্ত দেখা value, আর value = সেই value-র index। এতে "complement কি আগে দেখেছি?" প্রশ্নের উত্তর average O(1)।

5. Why this data structure fits

Hash map-এর membership/lookup average O(1) — concept.md বলেছে unsorted array-তে "এই value আছে কিনা" খোঁজা O(n), কিন্তু dict-এ O(1)। প্রতিটা element-এ আমরা একবার lookup করি (complement আছে?) আর একবার insert করি (নিজেকে রাখি) — দুটোই O(1), তাই পুরোটা O(n)।

6. Real-life analogy

ভাবো তুমি দোকানে দাঁড়িয়ে, হাতে 9 টাকা। প্রতিটা জিনিসের দাম দেখে ভাবছ — "এটা কিনলে আর কত টাকার জিনিস লাগবে?" সেই বাকি টাকার জিনিস তুমি একটা মনে-রাখা list-এ আগে দেখেছ কিনা চট করে মিলিয়ে নাও। list-টাই hash map।

7. Visual explanation

nums = [2, 7, 11, 15], target = 9:

seen (dict) শুরুতে খালি: {}

x=2  (i=0): need 9-2=7, seen-এ নেই  -> seen = {2:0}
x=7  (i=1): need 9-7=2, seen-এ আছে! (2 -> index 0)
            -> উত্তর [0, 1]

8. Example input and output

Input : nums = [2, 7, 11, 15], target = 9 -> Output: [0, 1]
Input : nums = [3, 2, 4],      target = 6 -> Output: [1, 2]
Input : nums = [3, 3],         target = 6 -> Output: [0, 1]

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা জোড়া (i, j) ধরে দেখি যোগফল target হয় কিনা — দুটো nested loop।

for i in range(n):
    for j in range(i+1, n):
        if nums[i] + nums[j] == target:
            return [i, j]

10. Why brute force is slow

দুটো nested loop মানে প্রায় n*(n-1)/2 জোড়া পরীক্ষা — O(n^2)। array বড় হলে এটা ভয়ংকর ধীর। বারবার একই কাজ হচ্ছে: প্রতিটা element-এর জন্য বাকি পুরো array আবার scan করছি, অথচ আগে দেখা value গুলো মনে রাখলেই হতো।

11. Key observation

মূল observation: একটা element fix করলে, তার জোড়া একদমই নির্দিষ্ট — target - x, আর কিছু না। তাই সব জোড়া try করার দরকার নেই; শুধু এই একটাই দরকারি সংখ্যা আগে দেখেছি কিনা দেখলেই হয়।

12. Optimized intuition

একবারই বাঁ থেকে ডানে হাঁটো। প্রতিটা x-এ আগে জিজ্ঞাসা করো "target - x কি আগের কোনো index-এ দেখেছি?" — দেখে থাকলে জোড়া পেয়ে গেলে। না দেখলে x-কে তার index সহ dict-এ রেখে এগিয়ে যাও। এক pass, O(n)।

13. Thinking tweak

মোচড়: "সব জোড়া মেলাব" (O(n^2)) বদলে "প্রতিটা সংখ্যার একমাত্র দরকারি সঙ্গী আগে দেখেছি কিনা মনে রাখব" (O(n))। মনে-রাখাটাই hash map।

14. Step-by-step dry run

Input nums = [3, 2, 4], target = 6:

  1. শুরু: seen = {}।
  2. i=0, x=3: need 6-3=3; seen-এ নেই → seen = {3:0}।
  3. i=1, x=2: need 6-2=4; seen-এ নেই → seen = {3:0, 2:1}।
  4. i=2, x=4: need 6-4=2; seen-এ আছে (2 → index 1) → return [1, 2]।

15. Python solution

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:           # complement আগে দেখেছি?
            return [seen[need], i]
        seen[x] = i                # নিজেকে রেখে এগোও
    return []                      # (problem বলে উত্তর সবসময় আছে)

# ---- tests ----
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]
print("সব test pass!")

16. Line-by-line code explanation

  • seen = {} — এ পর্যন্ত দেখা value→index রাখার dict।
  • for i, x in enumerate(nums) — index আর value একসাথে নিয়ে একবার হাঁটা।
  • need = target - x — এই x-এর একমাত্র দরকারি জোড়া।
  • if need in seen — সেই জোড়া আগে দেখেছি কিনা, O(1) check।
  • return [seen[need], i] — আগের index আগে, এখনকার index পরে।
  • seen[x] = i — না মিললে নিজেকে future-এর জন্য রেখে যাও।

17. Output walkthrough

[2,7,11,15], 9: x=2 রাখা হয়, x=7-এ need=2 dict-এ পাওয়া যায় → [0,1], assert pass। [3,2,4], 6 দেয় [1,2]; [3,3], 6-এ প্রথম 3 রাখা হয়, দ্বিতীয় 3-এ need=3 পাওয়া যায় → [0,1]। শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা element-এ একবার O(1) lookup আর একবার O(1) insert; মোট এক pass।

19. Space complexity

O(n) — সবচেয়ে খারাপ ক্ষেত্রে প্রায় সব element dict-এ জমা হতে পারে।

20. Common mistakes

  • নিজেকে রাখার (seen[x] = i) আগে lookup না করা — তখন একই element-কে নিজের জোড়া বানিয়ে ফেলতে পারো (যেমন target = 2*x হলে)।
  • index-এর বদলে value ফেরত দেওয়া — problem index চায়।
  • duplicate value-তে ভয় পাওয়া — [3,3]-এ ঠিকই কাজ করে, কারণ প্রথম 3 রাখার পর দ্বিতীয় 3-এ complement মিলে যায়।

21. Which basic problem this inherits from

ভিত্তি: array traversal + hash-map membership। এটাই 3Sum (tracker #16) আর Subarray Sum Equals K (#15)-এর ভিত — দুটোই কোনো-না-কোনো complement আগে দেখেছি কিনা খোঁজে।

22. Similar harder problems

23. Pattern learned

Complement lookup with a hash map: সব জোড়া try না করে, "দরকারি সঙ্গী আগে দেখেছি?" — এক pass O(n)। Frequency/complement চিন্তার মূল।

24. Final summary

ভবিষ্যতের আমাকে: "জোড়া খুঁজতে হলে complement (target - x) hash map-এ আগে দেখেছি কিনা মেলাও।" "pair that sums to..." দেখলেই এই এক-pass dict trick মনে করবে।

25. JavaScript solution (with test cases)

complement lookup — JS-এ Map দিয়ে value→index রাখি; আগে খোঁজো, পরে নিজেকে রাখো।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function twoSum(nums, target) {
  const seen = new Map();             // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];  // complement আগে দেখেছি?
    seen.set(nums[i], i);             // না হলে নিজেকে রেখে এগোও
  }
  return [];                          // (problem বলে উত্তর সবসময় আছে)
}

// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(twoSum([2, 7, 11, 15], 9), [0, 1]), "2+7");
assert(eq(twoSum([3, 2, 4], 6), [1, 2]), "2+4");
assert(eq(twoSum([3, 3], 6), [0, 1]), "duplicate 3+3");
assert(eq(twoSum([-1, -2, -3, -4, -5], -8), [2, 4]), "negative");
console.log("সব JS test pass!");

JS টীকা: numeric key নিরাপদ রাখতে Map (plain object {}-এ key string হয়ে যায়, negative/বড় সংখ্যায় বিভ্রান্তি)। ক্রম জরুরি — আগে has(need), পরে set; উল্টালে target = 2*x হলে একই element-কে নিজের জোড়া বানিয়ে ফেলবে।

26. TypeScript solution (with test cases)

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();   // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i], i);
  }
  return [];
}

function expectArr(actual: number[], expected: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(expected)) {
    throw new Error(`FAIL ${msg}: [${actual}]`);
  }
}

expectArr(twoSum([2, 7, 11, 15], 9), [0, 1], "2+7");
expectArr(twoSum([3, 2, 4], 6), [1, 2], "2+4");
expectArr(twoSum([3, 3], 6), [0, 1], "3+3");
console.log("সব TS test pass!");

TS টীকা: Map<number, number> key/value দুটোই number-এ বাঁধে; আর has পেরোনোর পর get(need)! (non-null assertion) দিয়ে বলি মান নিশ্চিত আছে — type checker-এর সাথে যুক্তিটা মিলিয়ে রাখে।

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

  • Pair/complement খোঁজা: "দুটো জিনিস মিলে target" — দাম + ছাড়, দুই transaction মিলে নির্দিষ্ট অঙ্ক, ইত্যাদি।
  • Deduplication / seen-set: এক pass-এ "এটা আগে দেখেছি?" — duplicate detection, first-repeat খোঁজা।
  • Join / lookup acceleration: এক table hash করে অন্যটার সাথে O(1) lookup-এ মেলানো (hash join-এর সরল রূপ)।
  • Caching / memoization: computed মান key→value রেখে পরে instant ফেরত — Map-এর সাধারণ ব্যবহার। মূল pattern — "সব জোড়া না মিলিয়ে, একমাত্র দরকারি complement আগে দেখেছি কিনা hash-এ খোঁজা (O(n²) → O(n))" — Two Sum, 3Sum, subarray-sum-K জুড়ে বড় ছবিতে ফেরে।

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