𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 আপনাকে একটি অ্যারেতে (array) 'majority element' বা সংখ্যাগুরু উপাদানটি খুঁজে বের করতে বলে। সংখ্যাগুরু উপাদানটি n / 2 বারের বেশি উপস্থিত থাকে। আমরা ধরে নিচ্ছি যে এটি সবসময় বিদ্যমান থাকে।
আপনি এটি দুইভাবে সমাধান করতে পারেন।
পদ্ধতি ১: Map পদ্ধতি
এই পদ্ধতিতে প্রতিটি সংখ্যা কতবার উপস্থিত আছে তা গণনা করার জন্য একটি Map ব্যবহার করা হয়।
- কাউন্ট সংরক্ষণের জন্য একটি Map তৈরি করুন।
- অ্যারের মধ্য দিয়ে লুপ চালান।
- প্রতিটি সংখ্যার কাউন্ট আপডেট করুন।
- Map-এর মধ্য দিয়ে লুপ চালিয়ে এমন একটি সংখ্যা খুঁজুন যার কাউন্ট n / 2 এর বেশি।
Complexity:
- Time: O(n), কারণ আপনি দুটি ধারাবাহিক লুপ ব্যবহার করছেন।
- Space: O(n), কারণ ইউনিক (unique) উপাদানের সংখ্যার সাথে Map-এর আকার বৃদ্ধি পায়।
পদ্ধতি ২: Boyer-Moore Voting Algorithm
এটি কনস্ট্যান্ট (constant) মেমরি ব্যবহার করে সমস্যাটি সমাধান করার একটি অপ্টিমাইজড উপায়।
সংখ্যাগুলোকে দুটি প্রতিদ্বন্দ্বী দলের মতো চিন্তা করুন। প্রতিবার যখন একটি সংখ্যা অন্য একটি ভিন্ন সংখ্যার সাথে মিলিত হয়, তারা একে অপরকে বাতিল (cancel) করে দেয়। যেহেতু সংখ্যাগুরু উপাদানটি অর্ধেকের বেশি সময় উপস্থিত থাকে, তাই এটি সবসময় শেষ পর্যন্ত টিকে থাকবে।
এটি যেভাবে কাজ করে:
- একটি প্রার্থী (candidate) নির্বাচন করুন এবং কাউন্ট ০ সেট করুন।
- অ্যারের মধ্য দিয়ে লুপ চালান।
- যদি কাউন্ট ০ হয়, তবে বর্তমান সংখ্যাটিকে প্রার্থী হিসেবে সেট করুন।
- যদি বর্তমান সংখ্যাটি প্রার্থীর সাথে মিলে যায়, তবে কাউন্ট ১ বাড়িয়ে দিন।
- যদি না মিলে, তবে কাউন্ট ১ কমিয়ে দিন।
Complexity:
- Time: O(n), কারণ আপনি অ্যারের মধ্য দিয়ে মাত্র একবার যাচ্ছেন।
- Space: O(1), কারণ আপনি মাত্র দুটি ভেরিয়েবল ব্যবহার করছেন।
কেন এটি গুরুত্বপূর্ণ:
উভয় পদ্ধতিরই টাইম কমপ্লেক্সিটি (time complexity) হলো O(n)। তবে, দ্বিতীয় পদ্ধতিটি অনেক কম মেমরি ব্যবহার করে। এতে কোনো Map-এর প্রয়োজন হয় না। এটি বড় ডেটাসেটের (datasets) জন্য অনেক বেশি কার্যকর।
Source: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6