Skip to content

915. Partition Array into Disjoint Intervals

Description

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

Test cases are generated such that partitioning exists.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 2 <= nums.length <= 105
  • 0 <= nums[i] <= 106
  • There is at least one valid answer for the given input.

Solutions

Solution 1: Prefix Maximum + Suffix Minimum

To satisfy the requirements of the problem after partitioning into two subarrays, we need to ensure that the "maximum value of the array prefix" is less than or equal to the "minimum value of the array suffix".

Therefore, we can first preprocess the minimum value of the array suffix and record it in the mi array.

Then, we traverse the array from front to back, maintaining the maximum value mx of the array prefix. When we traverse to a certain position, if the maximum value of the array prefix is less than or equal to the minimum value of the array suffix, then the current position is the dividing point of the partition, and we can return it directly.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array nums.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        n = len(nums)
        mi = [inf] * (n + 1)
        for i in range(n - 1, -1, -1):
            mi[i] = min(nums[i], mi[i + 1])
        mx = 0
        for i, v in enumerate(nums, 1):
            mx = max(mx, v)
            if mx <= mi[i]:
                return i

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

 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> mi(n + 1, INT_MAX);
        for (int i = n - 1; ~i; --i) {
            mi[i] = min(nums[i], mi[i + 1]);
        }
        int mx = 0;
        for (int i = 1;; ++i) {
            int v = nums[i - 1];
            mx = max(mx, v);
            if (mx <= mi[i]) {
                return i;
            }
        }
    }
};

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

Comments