[LeetCode] Partition Array into Disjoint Intervals

Problem: 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.

Example:

Input: nums = [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Input: nums = [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Approach: A straight forward approach would be to check for every index 'i' where all nums[0]...nums[i-1]  are less than or equal to nums[i]...nums[n-1] where n is number of elements in the array nums but it will be an expensive solution.

If you look closely what we are trying to do here is to check 

Max(nums[0]...nums[i-1]) <= Min(nums[i]...nums[n-1]

Right! With keeping this mind we can maintain two arrays say maxLeft and minRight where maxLeft[i] is the Max(nums[0]...nums[i]) and minRight[i] is Min(nums[i]...nums[n-1]). We can easily generate these arrays in linear time.

Once the above arrays are generated we can just check if maxLeft[i-1] <= minRight[i] is true or false. If true then we can return i. 

If the above approach is clear then there is one minor optimisation we can do in terms of space. We can use a int variable instead of maintaining the maxLeft array. You can look at implementation to understand this approach. 

Implementation in C#:

    public int PartitionDisjoint(int[] nums) 

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        int[] minRight = new int[length];

        minRight[length - 1] = nums[length - 1];

        for (int i = length - 2; i >= 0; --i)

        {

            minRight[i] = Math.Min(minRight[i + 1], nums[i]);

        }

        int maxLeft = nums[0];

        for (int i = 0; i < length - 1; ++i)

        {

            maxLeft = Math.Max(maxLeft, nums[i]);

            if (maxLeft <= minRight[i + 1])

            {

                return i + 1;

            }

        }        

        return -1;

    }

Complexity: O(n)