জাভাস্ক্রিপ্টে লিনিয়ার টাইমে ফার্স্ট ডুপ্লিকেট আইটেম খুঁজে বের করা

সমস্যা বিবরণ

ন+১ সংখ্যক ইন্টিজার অ্যারে দেওয়া আছে (রেঞ্জ ১ থেকে n)। লিনিয়ার টাইম O(n) এবং O(n) স্পেসে একটা ডুপ্লিকেট নম্বর বের করতে হবে।

ইনপুট: [3, 4, 1, 4, 1] → আউটপুট: ১ বা ৪ (যেকোনো একটি)

সমাধান

const arr = [3, 4, 1, 4, 1];

const findRepeatedNumber = (arr = []) => {
  const set = new Set();
  for (const item of arr) {
    if (set.has(item)) {
      return item;
    }
    set.add(item);
  }
  return -1;
};

console.log(findRepeatedNumber(arr)); // 4

আউটপুট

4

ব্যাখ্যা

• Set দিয়ে সিন দেখা এলিমেন্ট O(1) টাইমে চেক করা যায়।
• টোটাল টাইম কমপ্লেক্সিটি O(n), স্পেস কমপ্লেক্সিটি O(n)।
• যদি কনস্ট্রেইন্ট অনুযায়ী ১ থেকে n রেঞ্জ থাকে, তবে ফ্লয়েডের টoise অ্যান্ড হেয়ার অ্যালগরিদম দিয়ে O(1) স্পেসেও করা যায়।