Split the List into Two Parts

Given a list of integers nums, return whether you can partition the list into two non-empty sublists such that every number in the left sublist is strictly less than every number in the right sublist.

Constraints
n ≤ 100,000 where n is the length of nums.
Example 1
Input
nums = [5, 3, 2, 7, 9]
Output
true
Explanation
We can split the list into left = [5, 3, 2] and right = [7, 9]

Split List/Array by Prefix Max and Suffix Min

We need two arrays to store the prefix maximum and suffix minimum. Then, we can iterate each position to see if the left maximum (prefix) is strictly smaller than the right minimum (suffix).

bool splitList(vector<int>& nums) {
    if (nums.empty()) return true;
    int sz = static_cast<int>(nums.size());
    vector<int> leftMax(sz), rightMin(sz);
    leftMax[0] = nums[0];
    rightMin.back() = nums.back();
    for (int i = 1; i < sz; ++ i) {
        leftMax[i] = max(leftMax[i - 1], nums[i]);
    }
    for (int i = sz - 2; i >= 0; -- i) {
        rightMin[i] = min(rightMin[i + 1], nums[i]);
    }
    for (int i = 0; i < sz - 1; ++ i) {
        if (leftMax[i] < rightMin[i + 1]) {
            return true;
        }
    }
    return false;
}

The time complexity is O(N) as we need to scan the given list three times (constant number of times). And the space requirement is O(N). We need to avoid the C++ pitfall of casting size() from unsigned int to int by using the static_cast which forces the type casting during the compliation time.

–EOF (The Ultimate Computing & Technology Blog) —