C++ में डिस्जॉइंट इंटरवल्स में ऐरे पार्टीशन (Partition Array into Disjoint Intervals)

मान लीजिए हमारे पास एक ऐरे A है, हमें इसे दो उपसरणियों left और right में विभाजित करना है जैसे कि:

• left उपसरणी में प्रत्येक तत्व right उपसरणी के प्रत्येक तत्व से कम या बराबर हो।

• left और right उपसरणी नॉन-खाली हों।

• left उपसरणी का सबसे छोटा संभव आकार हो।

ऐसे पार्टीशनिंग के बाद left की लंबाई खोजें। यह गारंटी है कि ऐसा पार्टीशनिंग मौजूद है।

उदाहरण के लिए, यदि इनपुट [5,0,3,8,6] है, तो आउटपुट 3 होगा, क्योंकि left ऐरे [5,0,3] और right उपसरणी [8,6] होगी।

समाधान दृष्टिकोण

1. n := A का आकार, maxx ऐरे बनाएं

2. minVal := A का अंतिम तत्व

3. maxx[0] = A[0], फिर maxx[i] = max(A[i], maxx[i-1])

4. ans := n-1 से शुरू करें

5. i = n-1 से 1 तक: minVal अपडेट करें, यदि minVal ≥ maxx[i-1] तो ans = i

6. ans लौटाएं

C++ कार्यान्वयन

#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; 
    } 
}; 

int main(){ 
    vector<int> v1 = {5,0,3,8,6}; 
    Solution ob; 
    cout << (ob.partitionDisjoint(v1)); 
    return 0; 
}

इनपुट

[5,0,3,8,6]

आउटपुट

3