Partition Array into Disjoint Intervals

LeetCode Q 915 - Partition Array into Disjoint Intervals

Given an array A, 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. It is guaranteed that such a partitioning exists.

Example 1:
Input: [5,0,3,8,6] ; Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:
Input: [1,1,1,0,6,12] ; Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Note:

• 2 <= A.length <= 30000
• 0 <= A[i] <= 10^6
• It is guaranteed there is at least one way to partition A as described.

Solution

Solution 1 :

Using two arrays, i.e.

• leftMax[i]: the maximum value between nums[0] and nums[i];
• rightMin[i]: the minimum value between nums[i] and nums[len - 1];

Traverse the array from left to right again, find the first position that
leftMax[i] <= rightMin[i + 1] and return i + 1;

Code:

public int partitionDisjoint(int[] A) {
	int len = A.length;
	int[] maxLeft = new int[len];
	int[] minRight = new int[len];
	
	maxLeft[0] = A[0];
	for (int i = 1; i < len; i++) {
		maxLeft[i] = Math.max(A[i], maxLeft[i - 1]);
	}
	
	minRight[len - 1] = A[len - 1];
	for (int i = len - 2; i >= 0; i--) {
		minRight[i] = Math.min(A[i], minRight[i + 1]);
	}
	
	for (int i = 0; i < len - 1; i++) {
		if (maxLeft[i] <= minRight[i + 1])
			return i + 1;
	}
	
	return -1;
}

Solution 2 :

Code:

public int partitionDisjoint(int[] A) {
	
	int localMax = 0, max = 0, partition = 0;
	
	for (int i = 0; i < A.length; i++) {
		
		if (A[i] > localMax) {
			partition = i;
			localMax = max;
		} else {
			max = Math.max(max, A[i]);
		}
	}

	return res;
}