Leetcode 915: Partition Array into Disjoint Intervals

Input: You are given a list of integers `nums`.

Example: Input: nums = [2, 5, 3, 7, 6]

Constraints:

• 2 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^6

• There is at least one valid answer for the given input.

Output: Return the length of the `left` subarray after partitioning the array as described.

Example: Output: 3

Constraints:

• The output should be an integer representing the length of the `left` subarray.

Goal: The goal is to find the smallest size of `left` where all elements in `left` are less than or equal to all elements in `right`.

Steps:

• Keep track of the maximum value encountered in the `left` subarray as you iterate through the array.

• If an element in the array is less than the maximum value of the `left`, update the partition point to include the previous elements in `left`.

• Once the partitioning is done, the size of `left` gives the required result.

Goal: The input array must have at least two elements, and there is always a valid partitioning.

Steps:

• The array `nums` has a length between 2 and 10^5.

• The values in `nums` are between 0 and 10^6.

Assumptions:

• The array will always contain a valid partitioning where the condition is satisfied.

• Input: Input: nums = [2, 5, 3, 7, 6]

• Explanation: For this array, the optimal partition is `left = [2, 5, 3]` and `right = [7, 6]`. The length of `left` is 3, so the answer is 3.

Approach: We need to find the smallest `left` subarray such that all elements in `left` are less than or equal to all elements in `right`. This can be done by tracking the maximum value in `left` and ensuring that the next element in the array is greater than or equal to this maximum value.

Observations:

• We can iterate through the array while keeping track of the maximum element in the left subarray.

• Once we find an element smaller than the maximum of the left subarray, we need to extend the left subarray to include that element.

• This approach involves linear traversal through the array, making it efficient enough for the input size constraints.

Steps:

• Initialize `max_i` and `cur` to the first element in the array.

• Iterate through the array, updating `cur` and checking if the current element violates the partition condition.

• Once a violation is detected, adjust the partition point and return the size of the left subarray.

Empty Inputs:

• The input array is guaranteed to have at least two elements, so no need to handle empty arrays.

Large Inputs:

• For large inputs, the solution must be efficient with a time complexity of O(n).

Special Values:

• If all elements are the same, the entire array could be in the `left` subarray.

Constraints:

• The constraints ensure that there is always a valid partition, so no need to handle invalid cases.

int partitionDisjoint(vector<int>& nums) {
    int n = nums.size();
    int max_i, cur, ans = 1;
    max_i = cur = nums[0];
    
    for(int i = 1; i < n; i++) {
        if(nums[i] < max_i) {
            max_i = cur;
            ans = i + 1;
        } else if (nums[i] > cur)
            cur = nums[i];
    }
    return ans;
}

1 : Function Declaration

int partitionDisjoint(vector<int>& nums) {

This is the declaration of the function 'partitionDisjoint', which takes a vector of integers as input.

2 : Variable Initialization

    int n = nums.size();

Initializes the variable 'n' to store the size of the 'nums' array.

3 : Variable Initialization

    int max_i, cur, ans = 1;

Declares three variables: 'max_i' for tracking the maximum value, 'cur' for the current element, and 'ans' for the partition index, initialized to 1.

4 : Variable Assignment

    max_i = cur = nums[0];

Assigns the first element of the array to both 'max_i' and 'cur' as the initial values.

5 : Loop

    for(int i = 1; i < n; i++) {

Starts a loop iterating through the array from the second element.

6 : Condition Check

        if(nums[i] < max_i) {

Checks if the current element is smaller than the previously tracked maximum value.

7 : Variable Update

            max_i = cur;

Updates the 'max_i' to be the current element 'cur' if a smaller element is found.

8 : Variable Update

            ans = i + 1;

Updates the partition index 'ans' to the current position 'i + 1'.

9 : Condition Check

        } else if (nums[i] > cur)

If the current element is larger than the current element 'cur', we update 'cur'.

10 : Variable Update

            cur = nums[i];

Updates the 'cur' variable to hold the current element if it's greater than the previous 'cur'.

11 : Return Statement

    return ans;

Returns the partition index 'ans'.

Best Case: O(n) where n is the length of the array

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear because we traverse the array once while keeping track of the partition.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant since we only need a few extra variables to track the current maximum and partition point.

Leetcode 915: Partition Array into Disjoint Intervals

Explore →