002 — Two Sum¶

Problem link ও উৎস

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 — "যা দরকার সেটা আগে দেখেছি কিনা" খোঁজা

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

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

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

যেমন nums = [2, 7, 11, 15], target = 9 হলে 2 + 7 = 9। তাই উত্তর indices [0, 1]; value [2, 7] ফেরত দিতে বলা হয়নি।

Input ও output¶

nums	target	উত্তর: দুটি index	মিলিয়ে দেখো
`[2, 7, 11, 15]`	9	`[0, 1]`	`nums[0] + nums[1] = 2 + 7`
`[3, 2, 4]`	6	`[1, 2]`	`nums[1] + nums[2] = 2 + 4`
`[3, 3]`	6	`[0, 1]`	মান সমান, কিন্তু দুটি আলাদা index

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

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

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

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

এটা 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)।

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

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

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

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

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

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

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা জোড়া (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]

কোথায় বেশি কাজ হচ্ছে¶

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

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

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

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

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

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

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

ছবিতে বোঝা¶

বর্তমান মান x হলে তার জোড়া need = target - x। রঙ করা বাক্সগুলোতে দেখো কীভাবে আগের index-এর সঙ্গে বর্তমানটি মেলে।

target 9: আগে দেখা 2-এর সঙ্গে নতুন 7 মেলে

১ · index 0-তে 2 পড়ি
চিহ্নিত ঘর: 02↑ i
17
211
315
need = 7। আগে কোনো মান দেখা হয়নি; তাই seen-এ 2 → 0 রাখি।
২ · index 1-তে 7 পড়ি
চিহ্নিত ঘর: 02↑ জোড়া
চিহ্নিত ঘর: 17↑ i
211
315
need = 2। seen জানায় 2 আছে index 0-তে। উত্তর [0, 1]; এখানেই থামি।

i	x	need	খোঁজার আগে seen: value → index	সিদ্ধান্ত
0	2	7	`{}`	7 নেই; `2 → 0` রাখো
1	7	2	`{2: 0}`	2 আছে; `[0, 1]` ফেরত দাও

seen-এ আগের index-গুলোই থাকে। তাই পাওয়া জোড়ায় একই element দুবার ব্যবহৃত হয় না।

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

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

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

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

Python¶

Python

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

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

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-এর জন্য রেখে যাও।

Output মিলিয়ে দেখা¶

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

JavaScript ও test cases¶

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

JavaScript

// 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-কে নিজের জোড়া বানিয়ে ফেলবে।

TypeScript ও test cases¶

TypeScript

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-এর সাথে যুক্তিটা মিলিয়ে রাখে।

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

সময়¶

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

অতিরিক্ত জায়গা¶

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

যে ভুলগুলো এড়াতে হবে¶

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

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

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

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

পরের অনুশীলন¶

3Sum (একটা element fix করে two-sum) — https://leetcode.com/problems/3sum/ (#16)
Two Sum II (sorted input, two pointers) — https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
Subarray Sum Equals K (prefix sum + complement) — https://leetcode.com/problems/subarray-sum-equals-k/ (#15)

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

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

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

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

কোথায় কাজে লাগে¶

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।