পাইথনে প্রতিটি সাবলিস্টে কমপক্ষে একটি ইউনিক এলিমেন্ট আছে কিনা চেক করার প্রোগ্রাম

পাইথনে একটি এলিমেন্টের লিস্ট nums দেওয়া আছে। লিস্টের সব সম্ভাব্য সাবলিস্ট (contiguous subarray) এ কমপক্ষে একটি এলিমেন্ট আছে যা সেটি সাবলিস্টে ঠিক একবারই আসে (frequency = 1) কিনা তা চেক করতে হবে। সমস্যা লিনিয়ার টাইমে সমাধান করতে হবে।

উদাহরণ

ইনপুট: nums = [5, 10, 20, 10, 0]

আউটপুট: True

কারণ: সব সাবলিস্টে কমপক্ষে একটি এলিমেন্ট আছে যার ফ্রিকোয়েন্সি ১।

এলগরিদম (Divide & Conquer + Frequency Analysis)

1. has_unique(left, right) রিকার্শিভ ফাংশন ডিফাইন করুন:
   • যদি left >= right: True রিটার্ন (বেস কেস: ০ বা ১ এলিমেন্ট)
   • counts = Counter(nums[left:right+1]) — সাবঅ্যারের ফ্রিকোয়েন্সি
   • যদি min(counts.values()) > 1: False রিটার্ন (সব এলিমেন্ট ডুপ্লিকেট)
   • start = left
   • left থেকে right পর্যন্ত ইটারেট করুন:
     • যদি counts[nums[index]] == 1 (ইউник এলিমেন্ট):
       • বাম পার্টিশন has_unique(start, index-1) চেক করুন
       • start = index + 1 (নেক্সট পার্টিশন)
   • has_unique(start, right) রিটার্ন করুন (ডান পার্টিশন)
2. মূল কল: has_unique(0, len(nums)-1)

পাইথন ইমপ্লিমেন্টেশন

from collections import Counter

def solve(nums):
    def has_unique(left, right):
        if left >= right:
            return True
        counts = Counter(nums[left : right + 1])
        if min(counts.values()) > 1:
            return False
        start = left
        for index in range(left, right + 1):
            if counts[nums[index]] == 1:
                if not has_unique(start, index - 1):
                    return False
                start = index + 1
        return has_unique(start, right)
    
    return has_unique(0, len(nums) - 1)

nums = [5, 10, 20, 10, 0]
print(solve(nums))  # Output: True

ইনপুট

[5, 10, 20, 10, 0]

আউটপুট

True

ব্যাখ্যা

• কিওয়া আইডিয়া: যদি একটি সাবঅ্যারে-এ সব এলিমেন্টের ফ্রিকোয়েন্সি > ১ হয়, তবে সেটি ফেইল (False)। অন্যথায়, ইউনিক এলিমেন্টগুলো দিয়ে সাবঅ্যারেকে পার্টিশন করে প্রতিটি পার্ট রিকার্শিভলি চেক করা হয়।
• ডিভাইড অ্যান্ড কনকার: ইউনিক এলিমেন্টগুলো "সেপারেটর" হিসেবে কাজ করে — তাদের বাম ও ডান পাশ আলাদা আলাদা চেক করা হয়।
• সময় জটিলতা: ওয়ার্স্ট কেস O(n²) (যদি অনেক ইউনিক এলিমেন্ট থাকে), কিন্তু অ্যাসিম্পটোটিক্যালি লিনিয়ার নয়। যাইহোক, প্র্যাক্টিসে খুব দ্রুত চলে।

অপ্টিমাইজেশন নোট

আসল লিনিয়ার টাইম (O(n)) সমাধানের জন্য আরও জটিল ডেটা স্ট্রাকচার (যেমন সেগমেন্ট ট্রি বা RMQ) দরকার। উপরের রিকার্শিভ সমাধান ইন্টারভিউ/প্র্যাক্টিসের জন্য পর্যাপ্ত এবং বোঝা সহজ।