পাইথনে অ্যারে স্প্লিট করে প্রথম অংশের সব উপাদান দ্বিতীয়াংশের চেয়ে ছোট হলে সর্বনিম্ন দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

একটি সংখ্যার তালিকা nums দেওয়া আছে। এটিকে দুটি অংশে ভাগ করতে হবে part1 এবং part2 যাতে part1-এর সব উপাদান part2-এর সব উপাদানের চেয়ে কম বা সমান। part1-এর সম্ভাব্য সর্বনিম্ন দৈর্ঘ্য (শূন্য না হলে) বের করুন।

উদাহরণ: nums = [3, 1, 2, 5, 4] হলে আউটপুট 3। কারণ part1 = [3, 1, 2] (সর্বোচ্চ ৩), part2 = [5, 4] (ন্যূনতম ৪)। ৩ ≤ ৪।

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

1. পুরো অ্যারেতে ন্যূনতম মান p খুঁজুন এবং এর প্রথম অবস্থান s নোট করুন।
2. p = max(nums[:s+1]) আপডেট করুন (প্রথম সেগমেন্টের সর্বোচ্চ)।
3. ans = s দিয়ে শুরু করুন।
4. বাকি উপাদান স্ক্যান করুন: যদি কোনো nums[i] < p পাওয়া যায়, তবে ans = i আপডেট করুন (স্প্লিট পয়েন্ট আরও ডানদিকে নিতে হবে)।
5. রিটার্ন ans + 1।

পাইথন কোড

def solve(nums):
    p = min(nums)
    s = 0
    for i in range(len(nums)):
        if nums[i] == p:
            s = i
            break
    p = max(nums[:s + 1])
    ans = s
    for i in range(s + 1, len(nums)):
        if nums[i] < p:
            ans = i
    return ans + 1

# টেস্ট
nums = [3, 1, 2, 5, 4]
print(solve(nums))  # আউটপুট: 3

ব্যাখ্যা

ন্যূনতম উপাদান অবশ্যই part1-এ থাকতে হবে। সেটি যেখানে পাওয়া যায়, সেখান পর্যন্ত part1 নিতে হয়। তারপর যেকোনো ছোট উপাদান পাওয়া গেলে স্প্লিট পয়েন্ট বাড়াতে হয়।

সময় জটিলতা

O(n) - দুইটি লিনিয়ার পাস। স্পেস O(1)।