{x}
blog image

Partition Array into Disjoint Intervals

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.

Solution Explanation: Partition Array into Disjoint Intervals

This problem asks us to partition an array into two contiguous subarrays, left and right, such that every element in left is less than or equal to every element in right, left and right are non-empty, and left has the minimum possible size. The solution involves finding the smallest index k where the maximum value in nums[:k] is less than or equal to the minimum value in nums[k:]. This index k represents the length of the left subarray.

Approach: Prefix Maximum and Suffix Minimum

The optimal approach uses two arrays to track prefix maximums and suffix minimums.

  1. Suffix Minimum Array (mi): We create an array mi of the same size as nums (or one element larger for convenience). mi[i] stores the minimum value among all elements from index i to the end of the array. This is calculated iteratively from right to left.

  2. Prefix Maximum Tracking: We iterate through the input array nums. In each iteration, we track the current maximum value (mx) seen so far in the prefix.

  3. Partition Point: For each index i, we check if the current prefix maximum (mx) is less than or equal to the minimum value in the suffix starting at i + 1 (mi[i + 1]). If this condition holds, we've found the smallest valid partition point, and we return i + 1 (the length of the left subarray).

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array. We perform a single pass to create the mi array and another pass to find the partition point.

  • Space Complexity: O(n) to store the mi array. The space used for mx is constant.

Code Implementation (Python3, Java, C++, Go)

The code implementations below follow the described algorithm. Note the slight variations in handling array indices and edge cases across different languages.

Python3

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        n = len(nums)
        mi = [float('inf')] * (n + 1)  # Initialize with infinity
        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): #enumerate starts from 1 to match the index
            mx = max(mx, v)
            if mx <= mi[i]:
                return i

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] mi = new int[n + 1];
        mi[n] = Integer.MAX_VALUE; // Initialize with maximum integer value
        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 <= n; ++i) { // Loop until we find a valid partition
            mx = Math.max(mx, nums[i - 1]);
            if (mx <= mi[i]) {
                return i;
            }
        }
        return -1; //Should not reach here given the constraints
    }
}

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        vector<int> mi(n + 1, INT_MAX); // Initialize with maximum integer value
        for (int i = n - 1; i >= 0; --i) {
            mi[i] = min(nums[i], mi[i + 1]);
        }
        int mx = 0;
        for (int i = 1; i <= n; ++i) { // Loop until we find a valid partition
            mx = max(mx, nums[i - 1]);
            if (mx <= mi[i]) {
                return i;
            }
        }
        return -1; //Should not reach here given the constraints
 
    }
};

Go

func partitionDisjoint(nums []int) int {
	n := len(nums)
	mi := make([]int, n+1)
	for i := range mi {
		mi[i] = math.MaxInt32 // Initialize with maximum integer value
	}
	for i := n - 1; i >= 0; i-- {
		mi[i] = min(nums[i], mi[i+1])
	}
	mx := 0
	for i := 1; i <= n; i++ { //Loop until we find a valid partition
		mx = max(mx, nums[i-1])
		if mx <= mi[i] {
			return i
		}
	}
	return -1 //Should not reach here given the constraints
 
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These code examples demonstrate the efficient approach to solve the "Partition Array into Disjoint Intervals" problem. Remember to handle potential edge cases and choose appropriate data types based on the constraints of the input.