অ্যারে থেকে ডুপ্লিকেট বাদ দেওয়া – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১৬

সমস্যা – একটি অ্যারে দেওয়া থাকবে যার প্রতিটি উপাদান একটি ইন্টিজার এবং অ্যারের সংখ্যাগুলো ছোট থেকে বড় ক্রমে সাজানো আছে। ওই অ্যারেতে যেসব সংখ্যা একাধিকবার আছে, সেসব সংখ্যা একটি রেখে অতিরিক্তগুলো বাদ দিতে হবে। আর এজন্য অতিরিক্ত কোনো অ্যারে ব্যবহার করা যাবে না, অর্থাৎ ইনপুট অ্যারেতেই কাজ করতে হবে। যেমন, ইনপুট যদি হয় [1, 1, 1, 2, 3, 3], তাহলে ডুপ্লিকেট (duplicate)-গুলো বাদ দিলে অ্যারেটি হবে [1, 2, 3, …]. এক্ষেত্রে প্রথম তিনটি সংখ্যার পরে বাকিগুলো কী হবে, সেটি বিবেচনা করা হবে না। আর অ্যারেটি পরিবর্তন করার পরে অ্যারেতে মোট কয়টি উপাদান আছে সেটি রিটার্ন করতে হবে। অর্থাৎ এই ইনপুটের জন্য অ্যারেটি পরিবর্তন করার পরে 3 রিটার্ন করতে হবে।

সমাধান – সমস্যাটিতে যদি বলা হত অতিরিক্ত অ্যারে ব্যবহার করা যাবে, তাহলে আমরা কী করতাম? একটি নতুন অ্যারে তৈরি করে সেখানে সংখ্যাগুলো এমনভাবে রাখতাম যেন কোনো সংখ্যা একবারের বেশি না আসে।

পাইথন দিয়ে ইমপ্লিমেন্ট করতে চাইলে, প্রথমে একটি লিস্ট তৈরি করতে হবে। লিস্টের প্রথম উপাদানটি হবে ইনপুট লিস্টের প্রথম উপাদান। তারপর ইনপুট লিস্টের প্রতিটি সংখ্যা পরীক্ষা করে দেখতে হবে কোনো সংখ্যা তার আগের সংখ্যার সমান কী না। যদি সমান না হয়, তাহলে সেটি নতুন লিস্টে নেওয়া হবে, আর সমান হলে কিছু করা হবে না। নিচের কোড দেখলেই সহজে বুঝতে পারা যাবে –

def remove_duplicates(nums):
    unique_nums = []
    unique_nums.append(nums[0])
    
    n = len(nums)
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            unique_nums.append(nums[i])

    return len(unique_nums)

প্রোগ্রামটি আরেকভাবে ইমপ্লিমেন্ট করা যায় –

def remove_duplicates(nums):
    unique_nums = list(set(nums))
    unique_nums.sort()
    return len(unique_nums)

এই ফাংশনটির কোড ছোট হলেও টাইম কমপ্লেক্সিটি বেশি। নতুন প্রোগ্রামাররা, বিশেষ করা যারা পাইথন দিয়ে কাজ করে, তারা অনেক সময় মনে করে যে, কোড কম লেখা মানে কোড বেশি ইফিশিয়েন্ট – এটি ভুল ধারণা। যাই হোক, আমাদের কিন্তু শর্ত ছিল যে, অতিরিক্ত মেমোরি ব্যবহার করা যাবে না। তাহলে কী করা যায়? প্রথম যেই ফাংশনটি লিখেছিলাম, সেটি আমরা এভাবেও লিখতে পারি –

def remove_duplicates(nums):
    n = len(nums)
    unique_nums = [0] * n
    unique_nums[0] = nums[0]
    current_index = 1
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            unique_nums[current_index] = nums[i]
            current_index += 1

    return current_index

এই ফাংশনটি ভালোভাবে লক্ষ করলে বুঝে ফেলা উচিত যে, unique_nums ব্যবহার না করলেও চলে। বুঝতে না পারলে একটু চিন্তা করতে হবে, তাহলেই বুঝে ফেলা উচিত।

আর ইন্টারভিউতে কিন্তু স্পেশাল কেস ঠিকভাবে হ্যান্ডেল করতে হবে। যেমন, এই প্রোগ্রামে ইনপুট যদি ফাঁকা অ্যারে বা লিস্ট হয়, তখন প্রোগ্রামটা 0 রিটার্ন করার বদলে ক্র্যাশ করবে, এটি ঠিক করতে হবে।

আশা করি নিচের দুটি সমস্যা সমাধান করতে তেমন বেগ পেতে হবে না –

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Facebook Comments

Leave a Reply