মান লেযিয়ে একটি অ্যারে A দেওয়া আছে, আমাদের এটি দুটি সাবঅ্যারে left এবং right-এ পার্টিশন করতে হবে যাতে -
left সাবঅ্যারের প্রতিটি এলিমেন্ট right সাবঅ্যারের প্রতিটি এলিমেন্টের চেয়ে কম বা সমান।
left এবং right সাবঅ্যারে দুটোই নন-এম্পটি।
left সাবঅ্যারের আকার সর্বনিম্ন।
এই পার্টিশনের পর left-এর দৈর্ঘ্য খুঁজে বের করতে হবে। এটি গ্যারান্টিদ করা আছে যে এমন পার্টিশন існу করে। ইনপুট [5,0,3,8,6] হলে আউটপুট ৩। left অ্যারে [5,0,3] এবং right [8,6]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
n := A.size(), maxx নামে n আকারের একটি অ্যারে তৈরি করুন
minVal := A[n-1]
maxx[0] := A[0]
i = 1 থেকে n-1 পর্যন্ত লুপ চালান
maxx[i] := max(A[i], maxx[i-1])
ans := A.size() - 1
i = n-1 থেকে ১ পর্যন্ত ডিক্রিমেন্ট করে লুপ চালান
minVal := min(minVal, A[i])
যদি minVal >= maxx[i-1] হয়, ans := i
ans রিটার্ন করুন
উদাহরণ
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
#include <bits/stdc++.h> using namespace std; class Solution { public: int partitionDisjoint(vector <int>& A) { int n = A.size(); vector <int> maxx(n); int minVal = A[n - 1]; maxx[0] = A[0]; for(int i = 1; i < n; i++){ maxx[i] = max(A[i], maxx[i - 1]); } int ans = A.size() - 1; for(int i = n - 1; i >= 1; i--){ minVal = min(minVal, A[i]); if(minVal >= maxx[i - 1]){ ans = i; } } return ans; } }; main(){ vector<int> v1 = {5,0,3,8,6}; Solution ob; cout << (ob.partitionDisjoint(v1)); }ইনপুট
[5,0,3,8,6]
আউটপুট
3
