JavaScript-এ দুটি অ্যারের ইন্টারসেকশন (Intersection) বের করা

ভূমিকা

দুটি অ্যারের ইন্টারসেকশন বের করা মানে: যেসব এলিমেন্ট **দুই অ্যারেতেই** আছে, সেগুলো বের করা। প্রতিটি এলিমেন্ট ততবারই থাকবে যতবার দুটি অ্যারেতেই পাওয়া যায় (multiset intersection)।

সম্পূর্ণ কোড

const arr1 = [1, 2, 43, 5, 3, 7, 7, 8, 4, 2];
const arr2 = [1, 1, 6, 6, 2, 78, 7, 2, 3, 7, 23, 5, 3];

const intersection = (arr1, arr2) => {
  const res = [];
  const { length: len1 } = arr1;
  const { length: len2 } = arr2;
  
  // ছোট অ্যারেটে লুপ করুন (অপ্টিমাইজেশন)
  const smaller = (len1 < len2 ? arr1 : arr2).slice();
  const bigger = (len1 >= len2 ? arr1 : arr2).slice();
  
  for (let i = 0; i < smaller.length; i++) {
    const idx = bigger.indexOf(smaller[i]);
    if (idx !== -1) {
      res.push(smaller[i]);
      bigger.splice(idx, 1, undefined); // একবার ব্যবহৃত হলে মুছে দিন
    }
  }
  return res;
};

console.log(intersection(arr1, arr2));
// আউটপুট: [1, 2, 5, 3, 7, 7, 2]

কোড ব্যাখ্যা

1. ছোট অ্যারে সিলেক্ট: লুপ ইটারেশন কমাতে
2. .slice(): কপি বানানো (মূল অ্যারে মিউটেট না হয়)
3. indexOf + splice: মিল পেলে রেজাল্টে পুশ, বড় অ্যারেতে থেকে মুছে ফেলা (ডুপ্লিকেট কাউন্ট ঠিক রাখতে)
4. undefined: splice-এ `undefined` দিয়ে প্লেসহোল্ডার রাখা (ইন্ডেক্স শিফট এড়াতে)

আউটপুট

[1, 2, 5, 3, 7, 7, 2]

⚠️ পারফরম্যান্স সমস্যা

`indexOf` + `splice` প্রতিটি ইটারেশনে O(n) করে, মোট **O(n×m)**। বড় অ্যারে হলে খুব ধীর।

অপ্টিমাইজড সংস্করণ: Hash Map (O(n+m))

const intersectionOptimized = (arr1, arr2) => {
  const freq = new Map();
  const result = [];
  
  // প্রথম অ্যারের ফ্রিকোয়েন্সি কাউন্ট
  for (const val of arr1) {
    freq.set(val, (freq.get(val) || 0) + 1);
  }
  
  // দ্বিতীয় অ্যারে স্ক্যান
  for (const val of arr2) {
    const count = freq.get(val) || 0;
    if (count > 0) {
      result.push(val);
      freq.set(val, count - 1);
    }
  }
  
  return result;
};

২. Set (যদি ইউনিক ইন্টারসেকশন লাগে - ডুপ্লিকেট বাদ)

const intersectionUnique = (arr1, arr2) => 
  [...new Set(arr1)].filter(x => new Set(arr2).has(x));

৩. Sort + Two Pointer (O(n log n) - স্পেস O(1))

const intersectionSorted = (arr1, arr2) => {
  const a = [...arr1].sort((a,b) => a-b);
  const b = [...arr2].sort((a,b) => a-b);
  const res = [];
  let i = 0, j = 0;
  
  while (i < a.length && j < b.length) {
    if (a[i] === b[j]) {
      res.push(a[i]);
      i++; j++;
    } else if (a[i] < b[j]) i++;
    else j++;
  }
  return res;
};

তুলনামূলক টেবিল

ব্যবহারিক অ্যাপ্লিকেশন

• ডেটাবেস JOIN: ইন-মেমরি ইন্টারসেকশন
• রিকমেন্ডেশন: কমন ইন্টারেস্ট/আইটেম
• সিকিউরিটি: কমন IP/ইউজার এজেন্ট ডিটেকশন
• বায়োইনফরম্যাটিক্স: জিন সিকোয়েন্স ওভারল্যাপ

সারাংশ

প্রোডাকশনে **Hash Map (Map অবজেক্ট)** ব্যবহার করুন - O(n+m) টাইম, সঠিক মাল্টিসেট হ্যান্ডলিং। সেট-ভিত্তিক পদ্ধতি শুধু ইউনিক ইন্টারসেকশনের জন্য।