915. Partition Array into Disjoint Intervals


Problem Description

The problem gives us an integer array called nums. We are required to split this array into two contiguous subarrays named left and right. The conditions for the split are:

  1. Every element in left should be less than or equal to every element in right.
  2. Both subarrays left and right should be non-empty.
  3. The subarray left should be as small as possible.

The goal is to return the length of the left subarray after partitioning it according to the rules mentioned above.

For clarity: If nums is [5,0,3,8,6], one correct partition could be left = [5,0,3] and right = [8,6], and we would return 3 because left has a length of 3.

Intuition

To solve this problem, we need to find the point where we can divide the array into left and right such that every element in left is smaller or equal to the elements in right.

Intuitively, as we traverse nums from left to right, we can keep track of the running maximum value. This value will indicate the highest number that must be included in the left subarray to satisfy the condition that all elements in left are smaller or equal to the elements in right.

Conversely, if we traverse the array from right to left, we can compute the running minimum. This minimum will provide us with the lowest value at each index that right can have.

The partition point should be at a place where the running maximum from the left side is less than or equal to the running minimum on the right side. This means that all values to the left of the partition point can form the left subarray, as they are guaranteed to be less than or equal to all values to the right of the partition point, which would form the right subarray.

We implement this logic by first creating an array mi to keep track of the minimum values from right to left. We then iterate from left to right, updating the running maximum mx. If at any position i, mx is less than or equal to mi[i], this means all elements before the current position can be part of the left subarray without violating the condition for the partition. We return i at this point since it represents the smallest possible size for the left subarray.

Solution Approach

The implementation follows a two-step process:

Step 1: Calculate Minimums From Right to Left

  • An array mi is initialized to store the running minimums from the right-hand side of the given nums array. This new array will have n+1 elements, where n is the length of nums, and is initialized with inf which represents infinity, guaranteeing that all actual numbers in nums are smaller than inf.
  • We iterate over nums starting from the last element to the first (right to left), updating mi such that every mi[i] contains the smallest element from nums[i] to nums[n-1].

Step 2: Find Partition Index

  • A variable mx is initialized to zero to keep track of the running maximum as we iterate through the array from left to right (important for determining the left subarray).
  • We iterate over the nums, using enumerate() to get both the index and the value at each step.
  • For each element in nums, we update mx to be the maximum of mx and the current element v. This running maximum represents the largest element that would have to be included in the left subarray for all elements in left to be smaller or equal to any element in right.
  • We then check if mx is less than or equal to mi[i] at this index. If this condition holds, it signifies that all elements up to this index in nums can form the left subarray, and they are all less than or equal to any element to their right. The index i is then returned as the size of left.

The algorithm described above uses a greedy approach to find the earliest point where the left could end, ensuring the conditions for the partition are met. By leveraging the pre-computed minimums and maintaining a running maximum, we can make this determination in a single pass over the input array after the initial setup, resulting in an efficient solution.

Here's a snippet of the implementation described:

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

The above python code snippet represents the full implementation of the solution approach for finding the length of the left subarray that satisfies the given partitioning conditions.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above.

Consider the array nums = [1, 1, 1, 0, 6, 12].

Step 1: Calculate Minimums From Right to Left

We need to initialize an array mi to store the running minimums from the right-hand side of the nums array.

Starting from the last element of nums, we fill mi as follows:

1mi = [inf, 12, 6, 6, 0, 0, inf]

(Note: The example is following 1-based indexes for this explanation)

Step 2: Find Partition Index

We traverse nums from left to right, keeping track of the running maximum (mx).

At each index, our mx and mi arrays will look like this:

  • Index i = 1, nums[i] = 1, mx = 1, mi[i] = 12. Condition mx <= mi[i] is True.
  • Index i = 2, nums[i] = 1, mx = 1, mi[i] = 6. Condition mx <= mi[i] is True.
  • Index i = 3, nums[i] = 1, mx = 1, mi[i] = 6. Condition mx <= mi[i] is True.
  • Index i = 4, nums[i] = 0, mx = 1, mi[i] = 0. Condition mx <= mi[i] is False.
  • Index i = 5, nums[i] = 6, mx = 6, mi[i] = 0. Condition mx <= mi[i] is False.
  • Index i = 6, nums[i] = 12, mx = 12, mi[i] = inf. Condition mx <= mi[i] is True.

As we can see, the last true condition for mx <= mi[i] occurred at index i = 3.

Therefore, the smallest index i we found that satisfies the conditions is 3. This suggests our left subarray should be [1, 1, 1], which has a length of 3, and that is the answer returned by our function.

The implementation for this example would execute the partitionDisjoint method on the array and return 3.

1solution = Solution()
2assert solution.partitionDisjoint([1, 1, 1, 0, 6, 12]) == 3

Python Solution

1class Solution:
2    def partitionDisjoint(self, nums: List[int]) -> int:
3        # Get the length of the input array
4        length = len(nums)
5      
6        # Create a list to store the minimum values encountered from right to left.
7        # Initialize each position with positive infinity for later comparison.
8        right_min = [float('inf')] * (length + 1)
9      
10        # Populate the right_min list with the minimum values from right to left.
11        for i in range(length - 1, -1, -1):
12            right_min[i] = min(nums[i], right_min[i + 1])
13      
14        # Initialize a variable to keep track of the maximum value seen so far from left to right.
15        left_max = 0
16      
17        # Iterate through the array to find the partition point.
18        for i, value in enumerate(nums):
19            # Update the running maximum value found in the left partition.
20            left_max = max(left_max, value)
21          
22            # Check if the left_max value is less than or equal to the right_min at the current position.
23            # This means all values to the left are less than or equal to values to the right, satisfying the condition.
24            if left_max <= right_min[i + 1]:
25                # Return the position as the partition index.
26                # i + 1 is used because the left partition includes the current element at index i.
27                return i + 1
28              
29        # The function will always return within the loop above, as the partition is guaranteed to exist.
30

Java Solution

1class Solution {
2    public int partitionDisjoint(int[] nums) {
3        int length = nums.length;
4        int[] minRightArray = new int[length + 1]; // This will store the minimum from right to left.
5        minRightArray[length] = nums[length - 1]; // Initialize the last element.
6      
7        // Fill minRightArray with the minimum values starting from the end.
8        for (int i = length - 1; i >= 0; --i) {
9            minRightArray[i] = Math.min(nums[i], minRightArray[i + 1]);
10        }
11      
12        int maxLeft = 0; // This will hold the maximum value in the left partition.
13      
14        // Iterate through the array to find the partition.
15        for (int i = 1; i <= length; ++i) {
16            int currentValue = nums[i - 1];      // Current value from nums array.
17            maxLeft = Math.max(maxLeft, currentValue); // Update maxLeft with the current value if it's greater.
18          
19            // If maxLeft is less than or equal to the minimum in the right partition,
20            // we have found the partition point.
21            if (maxLeft <= minRightArray[i]) {
22                return i; // The partition index is i.
23            }
24        }
25      
26        return 0; // Default return value if no partition is found (won't occur given problem constraints).
27    }
28}
29

C++ Solution

1#include <vector>
2#include <limits>
3
4class Solution {
5public:
6    int partitionDisjoint(std::vector<int>& nums) {
7        // Get the size of the input array.
8        int size = nums.size();
9      
10        // Create a vector to keep minimums encountered from the right side of the array.
11        // Initialize every element to INT_MAX.
12        std::vector<int> rightMinimums(size + 1, std::numeric_limits<int>::max());
13      
14        // Fill the rightMinimums array with the actual minimums encountered from the right.
15        for (int i = size - 1; i >= 0; --i) {
16            rightMinimums[i] = std::min(nums[i], rightMinimums[i + 1]);
17        }
18
19        // Track the maximum element found so far from the left.
20        int leftMax = 0;
21
22        // Iterate to find the partition point where every element on the left is less than or equal
23        // to every element on the right of the partition.
24        for (int i = 1; i <= size; ++i) {
25            int currentVal = nums[i - 1];
26            leftMax = std::max(leftMax, currentVal);
27
28            // If the current maximum of the left is less than or equal to the minimum of the right,
29            // we found our partition point.
30            if (leftMax <= rightMinimums[i]) {
31                // Return the partition index.
32                return i;
33            }
34        }
35
36        // Return 0 as a default (though the problem guarantees a solution will be found before this).
37        return 0;
38    }
39};
40

Typescript Solution

1function partitionDisjoint(nums: number[]): number {
2    // Get the size of the input array.
3    let size = nums.length;
4  
5    // Create an array to keep track of the minimums encountered from the right side of the array.
6    // Initialize every element to Infinity.
7    let rightMinimums: number[] = new Array(size + 1).fill(Infinity);
8  
9    // Populate the rightMinimums array with the actual minimum values encountered from the right.
10    for (let i = size - 1; i >= 0; --i) {
11        rightMinimums[i] = Math.min(nums[i], rightMinimums[i + 1]);
12    }
13
14    // Variable to track the maximum element found so far from the left side.
15    let leftMax = 0;
16
17    // Iterate through the array to find the partition point.
18    // All elements to the left of this point are less than or equal to every element on the right.
19    for (let i = 1; i <= size; ++i) {
20        let currentValue = nums[i - 1];
21        leftMax = Math.max(leftMax, currentValue);
22
23        // Check if the current maximum of the left is less than or equal to the minimum on the right.
24        if (leftMax <= rightMinimums[i]) {
25            // If so, the current index is the correct partition index, so return it.
26            return i;
27        }
28    }
29
30    // The problem statement guarantees a solution before reaching this point.
31    // Return 0 as a default (non-achievable in this problem context).
32    return 0;
33}
34

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the length of the array nums. This is because there are two separate for-loops that each iterate over the array once. The first for-loop goes in reverse to fill the mi array with the minimum value encountered so far from the right side of the array. The second for-loop finds the maximum so far and compares it with values in the mi array to find the partition point. Each loop runs independently of the other and both iterate over the array once, hence maintaining a linear time complexity.

The space complexity of the code is also O(n). This is due to the additional array mi that stores the minimum values up to the current index from the right side of the array. This mi array is the same length as the input array nums, so the space complexity is directly proportional to the input size.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫