Problem Description

Given an array of integers A, your task is to partition it into two (contiguous) subarrays left and right such that:

• Every element in left is less than or equal to every element in right.
• Both left and right are non-empty.
• left and right together cover all elements of A (i.e., they are a partition).

Return the smallest possible length of left after such a partitioning. The problem guarantees that there is at least one valid answer.

Key Constraints:

• There is exactly one valid answer for each input.
• Elements cannot be reused between left and right.
• The partition must be contiguous; left consists of A[0] to A[i] for some i, and right is A[i+1] to A[n-1].

Thought Process

At first glance, the problem seems to suggest checking every possible partition point and testing if all elements to the left are less than or equal to all elements to the right. This brute-force method would work, but it’s inefficient for large arrays.

To optimize, we recognize that for a partition at index i:

• The maximum value in left (i.e., max(A[0..i])) must be less than or equal to the minimum value in right (i.e., min(A[i+1..n-1])).

The challenge is to avoid recomputing maximums and minimums for every possible split, which would be slow. Instead, we can precompute prefix maximums and suffix minimums, allowing constant-time checks at each partition point.

Solution Approach

We solve the problem efficiently by precomputing useful information:

1. Prefix Maximums: For each index i, compute the largest value in A[0..i]. This tells us the maximum in left if we partition after i.
2. Suffix Minimums: For each index i, compute the smallest value in A[i..n-1]. This tells us the minimum in right if we partition after i.
3. Finding the Partition: Iterate through the array (except the last element, since right must be non-empty). For each i, check if prefix_max[i] ≤ suffix_min[i+1]. The smallest such i+1 is our answer.

Why this works: By precomputing prefix maximums and suffix minimums, we can check the partition condition in constant time at every potential split point, ensuring efficiency.

Example Walkthrough

Consider A = [5, 0, 3, 8, 6].

• Step 1: Compute prefix maximums
  prefix_max = [5, 5, 5, 8, 8]
  • prefix_max[0] = 5
  • prefix_max[1] = max(5, 0) = 5
  • prefix_max[2] = max(5, 0, 3) = 5
  • prefix_max[3] = max(5, 0, 3, 8) = 8
  • prefix_max[4] = max(5, 0, 3, 8, 6) = 8
• Step 2: Compute suffix minimums
  suffix_min = [0, 0, 3, 6, 6]
  • suffix_min[4] = 6
  • suffix_min[3] = min(8, 6) = 6
  • suffix_min[2] = min(3, 8, 6) = 3
  • suffix_min[1] = min(0, 3, 8, 6) = 0
  • suffix_min[0] = min(5, 0, 3, 8, 6) = 0
• Step 3: Find the partition
  • At i=0: prefix_max[0]=5, suffix_min[1]=0 → 5 > 0 (not valid)
  • At i=1: prefix_max[1]=5, suffix_min[2]=3 → 5 > 3 (not valid)
  • At i=2: prefix_max[2]=5, suffix_min[3]=6 → 5 ≤ 6 (valid!)
  Thus, the smallest left partition is [5, 0, 3] (length 3).

Time and Space Complexity

• Brute-force Approach: For each index, compute max of left and min of right (both O(n)), for O(n) possible partitions. Total time: O(n²). Space: O(1).
• Optimized Approach (Prefix/Suffix): Build prefix_max and suffix_min arrays in O(n) time and space. Then scan once for the partition in O(n).
  Time Complexity: O(n)
  Space Complexity: O(n) for the two arrays.
• Further Optimization: It's possible to achieve O(1) space by tracking only current left max and global max while scanning, but the prefix/suffix method is easier to understand.

Summary

The key insight is to recognize that a valid partition requires the maximum of the left to be less than or equal to the minimum of the right. By precomputing prefix maximums and suffix minimums, we can efficiently check all possible split points in O(n) time. This approach is elegant, easy to implement, and leverages common algorithmic techniques like prefix and suffix computations.

Code Implementation

class Solution:
    def partitionDisjoint(self, A):
        n = len(A)
        prefix_max = [0] * n
        suffix_min = [0] * n

        prefix_max[0] = A[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i-1], A[i])

        suffix_min[-1] = A[-1]
        for i in range(n-2, -1, -1):
            suffix_min[i] = min(suffix_min[i+1], A[i])

        for i in range(n-1):
            if prefix_max[i] <= suffix_min[i+1]:
                return i+1

class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        int n = A.size();
        vector<int> prefix_max(n), suffix_min(n);
        prefix_max[0] = A[0];
        for (int i = 1; i < n; ++i)
            prefix_max[i] = max(prefix_max[i-1], A[i]);
        suffix_min[n-1] = A[n-1];
        for (int i = n-2; i >= 0; --i)
            suffix_min[i] = min(suffix_min[i+1], A[i]);
        for (int i = 0; i < n-1; ++i)
            if (prefix_max[i] <= suffix_min[i+1])
                return i+1;
        return -1; // Should never reach here
    }
};

class Solution {
    public int partitionDisjoint(int[] A) {
        int n = A.length;
        int[] prefixMax = new int[n];
        int[] suffixMin = new int[n];
        prefixMax[0] = A[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = Math.max(prefixMax[i-1], A[i]);
        }
        suffixMin[n-1] = A[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMin[i] = Math.min(suffixMin[i+1], A[i]);
        }
        for (int i = 0; i < n-1; i++) {
            if (prefixMax[i] <= suffixMin[i+1]) {
                return i+1;
            }
        }
        return -1; // Should not reach here
    }
}

var partitionDisjoint = function(A) {
    const n = A.length;
    const prefixMax = new Array(n);
    const suffixMin = new Array(n);

    prefixMax[0] = A[0];
    for (let i = 1; i < n; i++) {
        prefixMax[i] = Math.max(prefixMax[i-1], A[i]);
    }
    suffixMin[n-1] = A[n-1];
    for (let i = n-2; i >= 0; i--) {
        suffixMin[i] = Math.min(suffixMin[i+1], A[i]);
    }
    for (let i = 0; i < n-1; i++) {
        if (prefixMax[i] <= suffixMin[i+1]) {
            return i+1;
        }
    }
};