C++-এ স্প্লিট লিস্ট: বাম দিয়ে ডান বড় পার্টিশন যাচাই

একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। এটি দুটি নন-ইম্পটি পার্টে ভাগ করা যায় কিনা যাতে বাম পার্টের সব সংখ্যা ডান পার্টের সব সংখ্যা থেকে স্ট্রিক্টলি ছোট হয়।

উদাহরণ

ইনপুট: [6, 4, 3, 8, 10]

আউটপুট: true

ব্যাখ্যা: বাম = [6,4,3] (ম্যাক্স=৬), ডান = [8,10] (মিন=৮)। ৬ < ৮ ✓

অ্যালগরিদম (প্রিফিক্স ম্যাক্স + সাফিক্স মিন)

1. left[i] = index i পর্যন্ত সর্বোচ্চ মান।
2. right[i] = index i থেকে শেষ পর্যন্ত সর্বনিম্ন মান।
3. যেকোনো i-তে (0 ≤ i < n-1) যদি left[i] < right[i+1] হয়, তবে true।

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

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

class Solution {
public:
    bool solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        left[0] = nums[0];
        right[n-1] = nums[n-1];
        
        for (int i = 1; i < n; i++)
            left[i] = max(left[i-1], nums[i]);
        for (int i = n-2; i >= 0; i--)
            right[i] = min(right[i+1], nums[i]);
        
        for (int i = 0; i < n-1; i++)
            if (left[i] < right[i+1])
                return true;
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {6, 4, 3, 8, 10};
    cout << ob.solve(v);
    return 0;
}

সময় জটিলতা

O(n) - তিনটি লিনিয়ার পাস। স্পেস O(n)।