Partition Array into Disjoint Intervals

Given an array A, 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. It is guaranteed that such a partitioning exists.

Example 1:

Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Note:

1. 2 <= A.length <= 30000

2. 0 <= A[i] <= 10^6

3. It is guaranteed there is at least one way to partition A as described.

// We can easily do in O(N) space with leftMax & rightMin Arrays
class Solution {
    // https://drive.google.com/file/d/1_5oQ8U-yjScAZprd8W_sgjGK84MjZDRE/view?usp=sharing
    // O(1) space solution
    public int partitionDisjoint(int[] A) {
        // partition variables
        int currentMax = A[0], index = 0;
        // Overall variables
        int max = A[0];
        for (int i = 1; i < A.length; i++) {
            max = Math.max(max, A[i]);
            // If the current element does not violates our partition
            if (A[i] >= currentMax)
                continue;
            // Else we need to increase our partition upto this point
            else {
                currentMax = max;
                index = i;
            }
        }
        return index + 1;
    }
}