How to 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:
2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

Bruteforce Algorithm to Partition Array into Disjoint Intervals

Obviously, we can bruteforce the possible parition solutions, and check if every element in left is less than or equalt to the numbers in the right partition. But this is slow. It will need O(N^2) time.

Preprocess the Max Left and Right Array

We can pre-process the array twice to obtain a max left and max right array. Then, we need to check when the first time we have maxLeft is smaller or equal to the maxRight.

It turns out we only need to allocate an O(N) array to store e.g. maxRight, and updating a current MaxLeft when we iterating the array from left.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        vector<int> minRight(A.size(), INT_MAX);
        minRight[A.size() - 1] = A.back();
        for (int i = A.size() - 2; i >= 0; -- i) {
            minRight[i] = min(minRight[i + 1], A[i]);
        }
        int maxLeft = -1;
        for (int i = 0; i + 1 < A.size(); ++ i) {
            maxLeft = max(maxLeft, A[i]);
            if (maxLeft <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return A.size(); // return something to make compiler happy
    }
};

class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        vector<int> minRight(A.size(), INT_MAX);
        minRight[A.size() - 1] = A.back();
        for (int i = A.size() - 2; i >= 0; -- i) {
            minRight[i] = min(minRight[i + 1], A[i]);
        }
        int maxLeft = -1;
        for (int i = 0; i + 1 < A.size(); ++ i) {
            maxLeft = max(maxLeft, A[i]);
            if (maxLeft <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return A.size(); // return something to make compiler happy
    }
};

O(N) time and O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —