915. Partition Array into Disjoint Intervals

Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:

• Every element in left is less than or equal to every element in right.
• left and right are non-empty.
• left has the smallest possible size.

Return the length of left after such a partitioning.

Test cases are generated such that partitioning exists.

• Time : O(n)
• Space : O(n)

class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        int n = A.size();
        vector<int> mi(n, INT_MAX);
        mi[n - 1] = A.back();
        for(int i = n - 2; i >= 0; i--) {
            mi[i] = min(mi[i + 1], A[i]);
        }
        for(int i = 0, ma = 0; i < n - 1; i++) {
            ma = max(ma, A[i]);
            if(mi[i] == A[i] and mi[i + 1] >= ma)
                return i + 1;
        }

        return -1;
    }
};

• Time : O(n)
• Space : O(1)

class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        int n = A.size(), left = A[0], ma = A[0], res = 1;
        for(int i = 0; i < n; i++) {
            ma = max(ma, A[i]);
            if(A[i] < left) {
                left = ma;
                res = i + 1;
            }
        }
        return res;
    }
};