Problem Explanation

The problem statement asks to partition a given array into two subarrays such that each element in the first array is less or equal than each element in the second array. The first array should be as small as possible, but at least one element needs to be included. The output should be the length of the first array.

In simpler terms, we can say we need to split the array into two partitions such that all the elements in the left partition are smaller than or equal to the elements in the right partition. We also need to make the left partition as small as possible without being empty.

For example, consider an array [1, 1, 1, 0, 6, 12], here, the left partition could be [1, 1, 1, 0] and the right partition could be [6, 12].

Solution Explanation

To solve this problem, we use a simple approach that involves a single pass through the array.

We initialize variables min and max. min is an array of the same size as the input array and max is initialized to the smallest possible integer. min keeps track of the minimum element in the array from the current position to the end of the array. max keeps track of the maximum element seen so far.

We first fill the min array in reverse order, with each position holding the minimum number among the current array's element and the next position in the min array. That way, for each index i in min, it'll hold the smallest element from i to the end of the array.

Next, we iterate over the input array from left to right. For each element in the input array, we update max to the maximum of the current max and the current element. Then, we check if max is less than or equal to the next element in our min array. If so, we've found our partition point as we're assured all numbers to the right of our current position are larger or equal max. We return the current position + 1 as the length of the left partition.

Code Explanation (using C++)

1
2c++
3// Adding necessary libraries
4#include <vector> // For std::vector
5#include <algorithm> // For std::min and std::max
6
7class Solution {
8public:
9    int partitionDisjoint(vector<int>& nums) {
10        int n = nums.size(); // number of elements in the given array
11        vector<int> min(n); // Define vector min with size n
12        min[n - 1] = nums[n - 1]; // Set last element of min as last element of array
13        int max = INT_MIN; // Set max to the smallest possible int
14
15        // Populate the min array
16        for (int i = n - 2; i >= 0; --i)
17            min[i] = std::min(min[i + 1], nums[i]);
18
19        // Find where to partition our array
20        for (int i = 0; i < n; ++i) {
21            max = std::max(max, nums[i]);
22            // Check if max is less or equal to next min, 
23            // If true we found our partition point
24            if (max <= min[i + 1])
25                return i + 1;
26        }
27
28        // This will never be reached due to problem constraints, but we need to satisfy the compiler
29        throw;
30    }
31};

This solution ensures that we find the smallest possible left partition while also guaranteeing that each element in the left partition is less than or equal to each element in the right partition.# Python Solution

1
2python
3def partitionDisjoint(nums):
4    n = len(nums)  
5    min = [0] * n  
6    min[n - 1] = nums[n - 1] 
7    max_ = float('-inf')  
8   
9    for i in range(n - 2, -1, -1):
10        min[i] = min(min[i + 1], nums[i])
11    
12    for i in range(n):
13        max_ = max(max_, nums[i])
14        if max_ <= min[i + 1]:
15            return i + 1

JavaScript Solution

1
2javascript
3var partitionDisjoint = function(nums) {
4    let n = nums.length;
5    let min = new Array(n);
6    min[n - 1] = nums[n - 1];
7    let max = Number.MIN_SAFE_INTEGER;
8
9    for (let i = n - 2; i >= 0; --i){
10        min[i] = Math.min(min[i + 1], nums[i]);
11    }
12
13    for (let i = 0; i < n; i++){
14        max = Math.max(max, nums[i]);
15        if (max <= min[i + 1]){
16            return i + 1;
17        }
18    }
19};

Java Solution

1
2java
3class Solution {
4    public int partitionDisjoint(int[] nums) {
5        int n = nums.length;
6        int[] min = new int[n];
7        min[n - 1] = nums[n - 1];
8        int max = Integer.MIN_VALUE;
9
10        for (int i = n - 2; i >= 0; i--){
11            min[i] = Math.min(min[i + 1], nums[i]);
12        }
13
14        for (int i = 0; i < n; i++){
15            max = Math.max(max, nums[i]);
16            if (max <= min[i + 1]){
17                return i + 1;
18            }
19        }
20
21        throw new IllegalArgumentException("No solution exists");
22    }
23}

These Python, JavaScript, and Java solutions also include the creation of a min array and a max value. These approaches follow the same logic, building a min array from right to left and then checking the condition from left to right, returning the partition point when the condition is met. They have a time complexity of O(n) and a space complexity of O(n), where n is size of array.