পাইথনে টার্গেটের চেয়ে বড় বা সমান যোগফলવાલা ন্যূনতম দৈর্ঘ্যের সাবলিস্ট বের করা

একটি সংখ্যার লিস্ট nums এবং একটি target দেওয়া আছে। যোগফল target-এর চেয়ে বড় বা সমান এমন ন্যূনতম দৈর্ঘ্যের সাবলিস্ট (Subarray) বের করতে হবে। না পেলে -১ রিটার্ন।

উদাহরণ: nums = [2, 11, -4, 17, 4], target = 19 → আউটপুট 2 (সাবলিস্ট [17, 4])।

সমাধানের ধাপসমূহ (Prefix Sum + Monotonic Deque)

ps := প্রিফিক্স সাম অ্যারে (শুরুতে ০)।
যদি কোনো একক এলিমেন্ট >= target হয়, ১ রিটার্ন করুন।
min_size := inf, q := [0] (মনোটোনিক ডিক), j := 0।
i = 1 থেকে len(ps) পর্যন্ত:
- j = min(j, len(q)-1)।
- যখন j < len(q) এবং ps[i] - ps[q[j]] >= target:
  - min_size = min(min_size, i - q[j])
  - j++
- যখন q খালি নয় এবং ps[i] <= ps[q[-1]]: q.pop()।
- q.append(i)।
min_size যদি inf নয় হয় তবে সেটি রিটার্ন, অন্যথায় -১।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, nums, target):
        ps = [0]
        for num in nums:
            ps += [ps[-1] + num]
            if num >= target:
                return 1
        min_size = float("inf")
        q = [0]
        j = 0
        for i in range(1, len(ps)):
            j = min(j, len(q) - 1)
            while j < len(q) and ps[i] - ps[q[j]] >= target:
                min_size = min(min_size, i - q[j])
                j += 1
            while q and ps[i] <= ps[q[-1]]:
                q.pop()
            q.append(i)
        return min_size if min_size < float("inf") else -1

ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))

ইনপুট

[2, 11, -4, 17, 4], 19