পাইথনে অ্যারে সাজাতে হলে ন্যূনতম দৈর্ঘ্যের অসাজা সাবঅ্যারে খুঁজে বের করা

একটি অসাজা অ্যারে দেওয়া থাকলে, ন্যূনতম দৈর্ঘ্যের সাবঅ্যারে খুঁজে বের করতে হবে যেটি সাজালে (sort করলে) পুরো অ্যারেটি সাজা হয়ে যায়।

উদাহরণ

ইনপুট: [2, 6, 4, 8, 10, 9, 15]

আউটপুট: 5 (সাবঅ্যারে: [6, 4, 8, 10, 9])

সমাধানের পদ্ধতি

1. অ্যারেটির একটি কপি বানিয়ে সাজানো (sorted) হয়।
2. মূল অ্যারে এবং সাজানো অ্যারে তুলনা করা হয়।
3. যে ইনডেক্সগুলোতে ভিন্ন মান আছে, সেগুলো সংগ্রহ করা হয়।
4. যদি কোনো পার্থক্য না থাকে, ০ ফেরত দিন।
5. যদি শুধু একটিই পার্থক্য থাকে, ১ ফেরত দিন।
6. অন্যথায় (শেষ পার্থক্য ইনডেক্স - প্রথম পার্থক্য ইনডেক্স + ১) ফেরত দিন।

পাইথন কোড

class Solution:
    def findUnsortedSubarray(self, nums):
        res = sorted(nums)
        r = []
        for i in range(len(res)):
            if nums[i] != res[i]:
                r.append(i)
        if not r:
            return 0
        if len(r) == 1:
            return 1
        return r[-1] - r[0] + 1

ob1 = Solution()
print(ob1.findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]))

ইনপুট

[2, 6, 4, 8, 10, 9, 15]

আউটপুট

5