915. Partition Array into Disjoint Intervals

Description

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

Constraints

1. 2 <= nums.length <= 30000

2. 0 <= nums[i] <= 106

3. It is guaranteed there is at least one way to partition nums as described.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        
        int[] minNums = new int[n];
        int min = Integer.MAX_VALUE;
        
        for(int i = n-1; i >= 0; i--) {
            min = Math.min(min, nums[i]);
            minNums[i] = min;
        }
        
        int[] maxNums = new int[n];
        int max = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; i++) {
            max = Math.max(max, nums[i]);
            maxNums[i] = max;
            if(i < n-1 && maxNums[i] <= minNums[i+1]) {
                return i+1;
            }
        }
        
        return n;
    }
}

Follow up