006 — Intersection of Two Arrays¶

Source¶

Original source: Classic hash set exercise
Platform: LeetCode — https://leetcode.com/problems/intersection-of-two-arrays/
Topic: hash set
Difficulty: Easy
Pattern: seen-set
Basic idea inherited from: set algebra (../operations.md) — intersection, union, difference

1. Problem in simple words¶

দুটো array nums1 আর nums2 দেওয়া আছে। তোমাকে এমন সব সংখ্যা ফেরত দিতে হবে যেগুলো দুটো array-তেই আছে। উত্তরে প্রতিটা সংখ্যা একবারই থাকবে (distinct), ক্রম যেকোনো।

nums1 = [1, 2, 2, 1], nums2 = [2, 2]  →  [2]
nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]  →  [4, 9]  (যেকোনো ক্রমে)

2. Which basic idea does this inherit from?¶

এটা দাঁড়িয়ে আছে set algebra-র উপর — ../operations.md-এ দেখা a & b (intersection), a | b (union), a - b (difference)। মূল চিন্তাটা seen-set (Pattern 4)-এরই রূপ: এক array-কে স্মৃতিতে (set-এ) তুলে রেখে, অন্য array-র প্রতিটা element সেখানে আছে কি না দেখা — "আগে দেখেছি?" প্রশ্নটাই।

3. What is the hidden math or logic?¶

লুকানো গণিতটা আক্ষরিক set intersection: দুই set-এর common element। duplicate গুরুত্বহীন বলে আগে দুই array-কে set বানিয়ে নিলে (১) duplicate আপনাআপনি মুছে যায়, (২) "দুই দিকে আছে কি" প্রশ্নটা O(1) membership-এ নেমে আসে। ফল: distinct common elements।

4. Which data structure is needed?¶

একটা hash set (Python-এ set)। দুই array-র অন্তত একটাকে set-এ তুলি (দ্রুত membership-এর জন্য), আর উত্তরও একটা set-এ জমাই (distinct রাখতে)।

5. Why this data structure fits¶

Set-এ x in first membership গড়ে O(1), আর set নিজে থেকেই duplicate ফেলে দেয় — দুটোই এই problem-এর সরাসরি চাহিদা। Nested-loop দিয়ে common খুঁজলে হতো O(n*m); set সেটাকে O(n+m)-এ নামায়, আর distinct-ও ফ্রি-তে দেয়।

6. Real-life analogy¶

দুই বন্ধুর Spotify playlist মেলানোর কথা ভাবো — তোমরা জানতে চাও কোন গানগুলো দুজনেরই আছে। তুমি এক বন্ধুর গানের নাম মাথায় তুলে নাও (set), তারপর অন্য বন্ধুর playlist-এর প্রতিটা গান নিয়ে দেখো "এটা কি আমার তালিকায় আছে?" মিললে common। দুজনের কারো playlist-এ একই গান দুবার থাকলেও common list-এ একবারই লেখো।

7. Visual explanation¶

nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]:

first = set(nums1) = {4, 9, 5}     (nums1-কে স্মৃতিতে তুললাম)

nums2 ঘুরে দেখি:
9 in first?  হ্যাঁ → result={9}
4 in first?  হ্যাঁ → result={9, 4}
9 in first?  হ্যাঁ → result={9, 4}   (set duplicate রাখে না)
8 in first?  না   → result={9, 4}
4 in first?  হ্যাঁ → result={9, 4}

result = {4, 9}  →  list করে ফেরত

8. Example input and output¶

Input : nums1 = [1, 2, 2, 1], nums2 = [2, 2]            Output: [2]
Input : nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]      Output: [4, 9]   (যেকোনো ক্রমে)
Input : nums1 = [1, 2, 3], nums2 = [4, 5, 6]            Output: []       (common নেই)
Edge  : nums1 = [], nums2 = [1, 2]                      Output: []       (একটা খালি)

9. Brute force thinking¶

প্রথম সরল চিন্তা: nums1-এর প্রতিটা element nums2-তে আছে কি না খুঁজে দেখি, থাকলে উত্তরে রাখি (আর duplicate এড়াতে আগে রেখেছি কি না দেখি)।

result = []
nums1-এর প্রতিটা x:
    x যদি nums2-তে থাকে এবং result-এ না থাকে:
        result-এ x যোগ করো
return result

10. Why brute force is slow¶

x in nums2 প্রতিবার O(m), আর nums1-এর প্রতিটা element-এর জন্য সেটা = মোট O(n*m)। উপরন্তু x in result check-ও list-এ O(k)। অথচ set membership O(1), তাই বারবার পুরো array scan করাটাই অপচয়।

11. Key observation¶

মূল observation: duplicate উত্তরের কোনো মানে রাখে না, আর "common কি না" = membership প্রশ্ন। দুই কথা মিলিয়ে দেখায় — set-ই নিখুঁত হাতিয়ার: membership O(1), আর distinct আপনাআপনি।

12. Optimized intuition¶

nums1-কে একটা set first-এ তোলো। তারপর nums2-র প্রতিটা element নিয়ে দেখো সে first-এ আছে কি না — থাকলে একটা result set-এ যোগ করো (set নিজেই duplicate সামলায়)। শেষে result-কে list করে ফেরত দাও। সব O(n+m)।

13. Thinking tweak¶

মোচড়: "দুই array মেলাও" না ভেবে ভাবো "এক array-কে স্মৃতিতে তুলে রাখো, অন্যটায় membership জিজ্ঞেস করো।" এটাই seen-set; আর Python-এ পুরোটা এক লাইনে: set(nums1) & set(nums2)।

14. Step-by-step dry run¶

Input nums1 = [1, 2, 2, 1], nums2 = [2, 2]:

first = set(nums1) = {1, 2}।
result = set()।
nums2: 2 in first? হ্যাঁ → result = {2}; পরের 2 in first? হ্যাঁ → result = {2} (অপরিবর্তিত)।
list(result) = [2]।

15. Python solution¶

def intersection(nums1, nums2):
    first = set(nums1)              # এক array-কে স্মৃতিতে তোলো
    result = set()
    for x in nums2:
        if x in first:             # দুই দিকেই আছে?
            result.add(x)          # set নিজেই duplicate সামলায়
    return list(result)

# ---- tests ----  (set-এর order অনিশ্চিত, তাই sorted দিয়ে মেলাই)
assert sorted(intersection([1, 2, 2, 1], [2, 2])) == [2]
assert sorted(intersection([4, 9, 5], [9, 4, 9, 8, 4])) == [4, 9]
assert sorted(intersection([1, 2, 3], [4, 5, 6])) == []
assert sorted(intersection([], [1, 2])) == []
print("সব test pass!")

16. Line-by-line code explanation¶

first = set(nums1) — nums1-কে set-এ তুলি; এতে duplicate মুছে যায় আর membership O(1) হয়।
result = set() — common element জমানোর জায়গা; set বলে distinct থাকবে।
for x in nums2 — দ্বিতীয় array-র প্রতিটা element নিয়ে দেখি।
if x in first — এটা কি nums1-এও ছিল? থাকলে এটা common।
result.add(x) — common হলে যোগ করো; আগে থাকলে set কিছু বদলায় না।
return list(result) — set-কে list বানিয়ে ফেরত (problem list চায়)।

এক-লাইনের Pythonic বিকল্প: return list(set(nums1) & set(nums2)) — & সরাসরি set intersection (../operations.md)।

17. Output walkthrough¶

[1,2,2,1] ও [2,2]: first={1,2}, nums2-র 2 দুটোই common কিন্তু set-এ একবার → [2]। [4,9,5] ও [9,4,9,8,4]: common {4,9} → sorted [4,9]। কোনো common না থাকলে []। এক array খালি হলেও []। শেষে print: সব test pass!।

18. Time complexity¶

O(n + m) — দুই array একবার করে; set তৈরি ও membership গড়ে O(1) প্রতি element।

19. Space complexity¶

O(n + m) — first set আর result set, worst case-এ প্রায় সব element ধরে।

20. Common mistakes¶

উত্তরে duplicate রেখে দেওয়া — problem distinct চায়; result-ও set হওয়া দরকার (বা শেষে dedupe)।
বড় array-টাকে set-এ তুলে ছোটটায় loop করা — উল্টোটা (ছোটটা set, বড়টায় loop) সাধারণত একটু কম memory খায়; functionally দুটোই ঠিক।
list-এ membership দিয়ে করা (x in nums1) — তখন আবার O(n*m); আসল লাভ set membership থেকেই।

21. Which basic problem this inherits from¶

ভিত্তি: seen-set (Pattern 4) + set algebra। ../operations.md-র set-operations অংশ (&, |, -) আর ../patterns.md-র Pattern 4 দেখো।

22. Similar harder problems¶

Intersection of Two Arrays II — https://leetcode.com/problems/intersection-of-two-arrays-ii/ (duplicate গুনে রাখতে হয় — Counter লাগে)
Contains Duplicate — https://leetcode.com/problems/contains-duplicate/ (এই tracker-এর #2; এক array-তেই membership)
Longest Consecutive Sequence — https://leetcode.com/problems/longest-consecutive-sequence/ (#12; set-এ পুরো array, smart run-গোনা)

23. Pattern learned¶

Seen-set / set algebra: এক collection-কে set-এ তুলে অন্যটায় membership জিজ্ঞেস করো — intersection/union/difference সবই এই চালের রূপ।

24. Final summary¶

ভবিষ্যতের আমাকে: "common element / দুই দিকে আছে কি / distinct" শুনলেই set। এক array স্মৃতিতে, অন্যটায় membership; আর duplicate-এর ঝামেলা set নিজেই মুছে দেয়। Python-এ চটজলদি: set(a) & set(b)।

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