Partition Array into Disjoint Intervals

 

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int size = nums.size();
        vector<int> forward(size);
        vector<int> backward(size);
        
        backward[size - 1] = nums[size - 1];
        for (int i = size - 2; i >= 0; --i)
            backward[i] = min(backward[i + 1], nums[i]);
            
        forward[0] = nums[0];
        for (int i = 0; i < size - 1; ++i) {
            if (i > 0)
                forward[i] = max(forward[i - 1], nums[i]);
            if (forward[i] <= backward[i + 1])
                return i + 1;
        }
        return 0;
    }
};

 

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int size = nums.size();
        int max_ = nums[0];
        int cur_ = nums[0];
        int ans = 1;
        
        for (int i = 1; i < size; ++i) {
            if (cur_ > nums[i]) {
                ans = i + 1;
                cur_ = max_;
            }
            
            max_ = max(max_, nums[i]);
        }
        return ans;
    }
};

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3823/