Problem

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 ofleft after such a partitioning.

Test cases are generated such that partitioning exists.

Examples

Example 1

1
2
3
4
5
6
7


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

Example 2

1
2
3
4
5
6
7


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

Constraints

  • 2 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^6
  • There is at least one valid answer for the given input.

Solution

Method 1 – Prefix Max and Suffix Min

Intuition

To ensure every element in left is less than or equal to every element in right, we can precompute the maximum value up to each index from the left and the minimum value from each index to the right. The smallest partition point is where the left max is less than or equal to the right min.

Approach

  1. Compute an array left_max where left_max[i] is the maximum of nums[0..i].
  2. Compute an array right_min where right_min[i] is the minimum of nums[i..n-1].
  3. Find the smallest index i where left_max[i] <= right_min[i+1].
  4. Return i+1 as the length of left.

Code

 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>& nums) {
        int n = nums.size();
        vector<int> left_max(n), right_min(n);
        left_max[0] = nums[0];
        for (int i = 1; i < n; ++i)
            left_max[i] = max(left_max[i-1], nums[i]);
        right_min[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i)
            right_min[i] = min(right_min[i+1], nums[i]);
        for (int i = 0; i < n-1; ++i) {
            if (left_max[i] <= right_min[i+1])
                return i+1;
        }
        return n;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func partitionDisjoint(nums []int) int {
    n := len(nums)
    leftMax := make([]int, n)
    rightMin := make([]int, n)
    leftMax[0] = nums[0]
    for i := 1; i < n; i++ {
        if nums[i] > leftMax[i-1] {
            leftMax[i] = nums[i]
        } else {
            leftMax[i] = leftMax[i-1]
        }
    }
    rightMin[n-1] = nums[n-1]
    for i := n-2; i >= 0; i-- {
        if nums[i] < rightMin[i+1] {
            rightMin[i] = nums[i]
        } else {
            rightMin[i] = rightMin[i+1]
        }
    }
    for i := 0; i < n-1; i++ {
        if leftMax[i] <= rightMin[i+1] {
            return i+1
        }
    }
    return n
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n], rightMin = new int[n];
        leftMax[0] = nums[0];
        for (int i = 1; i < n; i++)
            leftMax[i] = Math.max(leftMax[i-1], nums[i]);
        rightMin[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--)
            rightMin[i] = Math.min(rightMin[i+1], nums[i]);
        for (int i = 0; i < n-1; i++) {
            if (leftMax[i] <= rightMin[i+1])
                return i+1;
        }
        return n;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun partitionDisjoint(nums: IntArray): Int {
        val n = nums.size
        val leftMax = IntArray(n)
        val rightMin = IntArray(n)
        leftMax[0] = nums[0]
        for (i in 1 until n) leftMax[i] = maxOf(leftMax[i-1], nums[i])
        rightMin[n-1] = nums[n-1]
        for (i in n-2 downTo 0) rightMin[i] = minOf(rightMin[i+1], nums[i])
        for (i in 0 until n-1) {
            if (leftMax[i] <= rightMin[i+1]) return i+1
        }
        return n
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def partitionDisjoint(self, nums: list[int]) -> int:
        n = len(nums)
        left_max = [0] * n
        right_min = [0] * n
        left_max[0] = nums[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i-1], nums[i])
        right_min[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            right_min[i] = min(right_min[i+1], nums[i])
        for i in range(n-1):
            if left_max[i] <= right_min[i+1]:
                return i+1
        return n
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut left_max = vec![0; n];
        let mut right_min = vec![0; n];
        left_max[0] = nums[0];
        for i in 1..n {
            left_max[i] = left_max[i-1].max(nums[i]);
        }
        right_min[n-1] = nums[n-1];
        for i in (0..n-1).rev() {
            right_min[i] = right_min[i+1].min(nums[i]);
        }
        for i in 0..n-1 {
            if left_max[i] <= right_min[i+1] {
                return (i+1) as i32;
            }
        }
        n as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    partitionDisjoint(nums: number[]): number {
        const n = nums.length;
        const leftMax = Array(n).fill(0);
        const rightMin = Array(n).fill(0);
        leftMax[0] = nums[0];
        for (let i = 1; i < n; i++)
            leftMax[i] = Math.max(leftMax[i-1], nums[i]);
        rightMin[n-1] = nums[n-1];
        for (let i = n-2; i >= 0; i--)
            rightMin[i] = Math.min(rightMin[i+1], nums[i]);
        for (let i = 0; i < n-1; i++) {
            if (leftMax[i] <= rightMin[i+1])
                return i+1;
        }
        return n;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We scan the array three times (for left max, right min, and the answer).
  • 🧺 Space complexity: O(n), for the two auxiliary arrays left_max and right_min.