C++-এ K-এর চেয়ে বড় সমান সাবঅ্যারে সামের শর্টেস্ট দৈর্ঘ্য

সমস্যা বিবরণ

অ্যারে A এবং K দেওয়া থাকলে, যোগফল K-এর চেয়ে বড় বা সমান হয় এমন ন্যূনতম দৈর্ঘ্যের সংলগ্ন সাবঅ্যারে বের করতে হবে। না থাকলে -1।

উদাহরণ

A = [5,3,-2,2,1], K = 6 → আউটপুট = 2 (সাবঅ্যারে: [5,3])

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

প্রিফিক্স সাম + মনোটোনিক ডিক (Deque) ব্যবহার করা হয়।
প্রিফিক্স সাম আরে বানানো হয়।
ডিকতে ইনডেক্স রাখা হয় যাতে প্রিফিক্স সাম বর্ধমান ক্রমে থাকে।
প্রতিটি i-তে ডিকের ফ্রন্ট থেকে বৈধ সাবঅ্যারে চেক করা হয়।
সময় জটিলতা: O(N)।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int> &A, int K) {
        int n = A.size();
        int ans = n + 1;
        deque<int> dq;
        
        for (int i = 0; i < n; i++) {
            if (i > 0) A[i] += A[i - 1];
            if (A[i] >= K) ans = min(ans, i + 1);
            
            while (!dq.empty() && A[i] - A[dq.front()] >= K) {
                ans = min(ans, i - dq.front());
                dq.pop_front();
            }
            while (!dq.empty() && A[i] <= A[dq.back()])
                dq.pop_back();
            dq.push_back(i);
        }
        return ans == n + 1 ? -1 : ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,3,-2,2,1};
    cout << ob.shortestSubarray(v, 6);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {5,3,-2,2,1}, 6

আউটপুট: 2