JavaScript-এ প্রথম রিপিটিং ক্যারেক্টার/এলিমেন্ট খুঁজে বের করা

ভূমিকা

একটি অ্যারে (স্ট্রিং বা নম্বর) দেয়া থাকলে, যেখানে কোনো এলিমেন্ট একবারের বেশি বার আসে, সেটির **প্রথম occurrence-এর ইন্ডেক্স** রিটার্ন করতে হবে। যদি কোনো রিপিটিং এলিমেন্ট না থাকে তবে -1 রিটার্ন করবে।

সম্পূর্ণ কোড

const arr = [12, 4365, 76, 43, 76, 98, 5, 31, 4];
const secondArr = [6, 8, 9, 32, 1, 76, 98, 0, 65, 878, 90];

const findRepeatingIndex = (arr) => {
  const map = {};
  for (let i = 0; i < arr.length; i++) {
    if (map[arr[i]]) {
      return map[arr[i]]; // প্রথম occurrence-এর ইন্ডেক্স
    } else {
      map[arr[i]] = i; // প্রথমবার দেখতে পেলে ইন্ডেক্স সংরক্ষণ
    }
  }
  return -1; // কোনো রিপিট নেই
};

console.log(findRepeatingIndex(arr));       // 2 (76 ইনডেক্স ২-এ প্রথম আসেছে)
console.log(findRepeatingIndex(secondArr)); // -1 (কোনো রিপিট নেই)

কোড ব্যাখ্যা

Map অবজেক্ট: কী = এলিমেন্ট, ভ্যালু = প্রথম occurrence-এর ইন্ডেক্স
ইটারেশন: বাম থেকে ডান স্ক্যান
চেক: এলিমেন্ট map-এ আছে কিনা
হ্যাঁ হলে: সংরক্ষিত ইন্ডেক্স রিটার্ন (প্রথম occurrence)
না হলে: বর্তমান ইন্ডেক্স map-এ সংরক্ষণ

আউটপুট

2
-1

অ্যালগরিদম বিশ্লেষণ

Time: O(n) - এক পাস স্ক্যান
Space: O(k) - k = ইউনিক এলিমেন্ট সংখ্যা
সর্বোত্তম সম্ভব কমপ্লেক্সিটি

বিকল্প পদ্ধতিগুলো

১. Map অবজেক্ট (ES6+ - বেটার পারফরম্যান্স)

const findRepeatingIndex = (arr) => {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(arr[i])) return seen.get(arr[i]);
    seen.set(arr[i], i);
  }
  return -1;
};

২. Set + findIndex (সংক্ষিপ্ত কিন্তু O(n²))

const findRepeatingIndex = (arr) => {
  const seen = new Set();
  const idx = arr.findIndex(x => seen.has(x) || !seen.add(x));
  return idx === -1 ? -1 : arr.indexOf(arr[idx]);
};

৩. স্ট্রিং-এর জন্য (ক্যারেক্টার লেভেল)

const firstRepeatingChar = (str) => {
  const seen = new Set();
  for (let i = 0; i < str.length; i++) {
    if (seen.has(str[i])) return { char: str[i], index: i };
    seen.add(str[i]);
  }
  return null;
};

console.log(firstRepeatingChar("hello")); // { char: 'l', index: 2 }

৪. প্রথম নন-রিপিটিং ক্যারেক্টার (ভিন্ন সমস্যা)

const firstNonRepeating = (arr) => {
  const freq = new Map();
  for (const x of arr) freq.set(x, (freq.get(x) || 0) + 1);
  for (let i = 0; i < arr.length; i++) {
    if (freq.get(arr[i]) === 1) return i;
  }
  return -1;
};

স্ট্রিং-এ প্রয়োগ

const firstRepeatingCharIndex = (str) => {
  const map = {};
  for (let i = 0; i < str.length; i++) {
    if (map[str[i]] !== undefined) return map[str[i]];
    map[str[i]] = i;
  }
  return -1;
};

console.log(firstRepeatingCharIndex("abca")); // 0 (a ইনডেক্স ০-এ)
console.log(firstRepeatingCharIndex("abc"));  // -1

সারাংশ

হ্যাশ ম্যাপ (অবজেক্ট বা Map) ব্যবহার করে O(n) টাইমে প্রথম রিপিটিং এলিমেন্ট খুঁজে বের করা যায়। এটি ইন্টারভিউয়ে খুবই কমন প্রশ্ন।