Partition Array into Disjoint Intervals

MEDIUM

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 <= 10⁵
0 <= nums[i] <= 10⁶
There is at least one valid answer for the given input.

Approaches

Checkout 3 different approaches to solve Partition Array into Disjoint Intervals. Click on different approaches to view the approach and algorithm in detail.

Two-Pass with Auxiliary Arrays

This approach improves upon the brute-force method by pre-calculating the necessary maximums and minimums to avoid redundant computations. We use two auxiliary arrays: one to store the running maximum from the left and another to store the running minimum from the right. This allows us to check the partition condition for any split point in constant time.

Algorithm

Create an integer array maxLeft of size N.
Traverse nums from left to right to populate maxLeft, where maxLeft[i] will store the maximum value in nums[0...i].
Create another integer array minRight of size N.
Traverse nums from right to left to populate minRight, where minRight[i] will store the minimum value in nums[i...N-1].
Finally, iterate from i = 0 to N-2.
For each i, check if maxLeft[i] <= minRight[i+1]. This is the partition condition max(left) <= min(right).
The first index i that satisfies this condition gives the smallest left partition. Return i + 1.

The core condition is max(nums[0...i]) <= min(nums[i+1...N-1]). Instead of recalculating these values in each iteration, we can precompute them.

Create an array maxLeft where maxLeft[i] stores the maximum value in the subarray nums[0...i]. This can be computed in a single pass from left to right.
Create an array minRight where minRight[i] stores the minimum value in the subarray nums[i...N-1]. This can be computed in a single pass from right to left.
With these arrays, we can check the condition for each i in O(1) time. We iterate from i = 0 to N-2 and check if maxLeft[i] <= minRight[i+1]. The first i that satisfies this gives the smallest left partition of length i+1.

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] maxLeft = new int[n];
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.max(maxLeft[i - 1], nums[i]);
        }

        int[] minRight = new int[n];
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = Math.min(minRight[i + 1], nums[i]);
        }

        for (int i = 0; i < n - 1; i++) {
            if (maxLeft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return -1; // Should not be reached
    }
}

Complexity Analysis

Time Complexity: O(N). We make three separate passes through the array (one for `maxLeft`, one for `minRight`, and one for the final check), each taking O(N) time. This simplifies to O(N).Space Complexity: O(N), as we use two auxiliary arrays, `maxLeft` and `minRight`, each of size N.

Pros and Cons

Pros:

Significantly more efficient than the brute-force approach with linear time complexity.
Guaranteed to pass within the time limits for the given constraints.

Cons:

Uses extra space proportional to the input size, which might be a concern for very large arrays in a memory-constrained environment.

Code Solutions

Checking out 3 solutions in different languages for Partition Array into Disjoint Intervals. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Partition Array into Disjoint Intervals

Data Structures:

Array