এই সমস্যায় আমরা একটি অ্যারে দেওয়া থাকলে, সেটিকে কতটুকু "চাঙ্ক" বা পার্টিশনে ভাগ করা যাবে যাতে প্রতিটি পার্টিশন আলাদাভাবে সর্ট করলে পুরো অ্যারেটি সর্টেড হয়ে যায়। অ্যারেটি হলো [0, 1, ..., n-1]-এর একটি পারমুটেশন।
উদাহরণস্বরূপ, অ্যারে [1,0,2,3,4] এর জন্য আউটপুট হবে 4, কারণ আমরা এটিকে [1,0], [2], [3], [4] - এই ৪টি চাঙ্কে ভাগ করতে পারি।
সমাধানের পদ্ধতি
ans = 0,maxVal = INT_MINইনিশিয়ালাইজ করুন।- অ্যারে ট্রাভার্স করুন।
- প্রতিটি ইন্ডেক্স
i-এmaxVal = max(maxVal, arr[i])আপডেট করুন। - যদি
maxVal == iহয়, তবেans++করুন (কারণ ০ থেকে i পর্যন্ত সব এলিমেন্ট এই চাঙ্কে আছে)। ansরিটার্ন করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int ans = 0;
int maxVal = INT_MIN;
int n = arr.size();
for (int i = 0; i < n; i++) {
maxVal = max(arr[i], maxVal);
if (maxVal == i) {
ans++;
}
}
return ans;
}
};
int main() {
Solution ob;
vector<int> v = {1, 0, 2, 3, 4};
cout << ob.maxChunksToSorted(v);
return 0;
}
ইনপুট
[1,0,2,3,4]
আউটপুট
4
