---

1. Problem Summary

You are given an integer array nums.

Your task is to partition the array into two contiguous parts:

left  = nums[0 ... i]
right = nums[i+1 ... n-1]

such that:

1. Every element in left is less than or equal to every element in right
2. left is non-empty
3. right is non-empty

You must return the smallest possible size of left, meaning the smallest index i + 1.

Example:

Input:  [5,0,3,8,6]
Valid partition:
 left  = [5,0,3]
 right = [8,6]
Output: 3

---

2. Key Insights

Insight 1: Left must contain all values up to its max

For partition to be valid:

max(left) <= min(right)

Insight 2: We only care about minimal left size

So we should stop at earliest index where condition holds.

Insight 3: Running maximum helps define left boundary

As we scan array, we track:

• globalMaxSoFar (max seen in entire scan)
• leftMax (max within left partition)

Insight 4: When violation occurs, expand left

If we encounter nums[i] < leftMax, then:

• Partition invalid
• Must extend left to include index i
• Update leftMax = globalMaxSoFar

This ensures future values re-evaluated against expanded left.

Insight 5: No need to precompute right minimums

One pass is enough.

---

3. Approach

Single pass tracking leftMax and globalMax

Steps:

1. Initialize: leftMax = nums[0] globalMax = nums[0] partitionIndex = 0
2. Loop i from 1 to n-1:
   • update globalMax = max(globalMax, nums[i])
   • if nums[i] < leftMax:
     • update partitionIndex = i
     • update leftMax = globalMax
3. At end, return partitionIndex + 1

PartitionIndex + 1 gives size of left part.

---

4. Time and Space Complexity

Time Complexity:

O(N)

Space Complexity:

O(1)

Uses only constant extra variables.

---

5. Java Solution

class Solution {
    public int partitionDisjoint(int[] nums) {
        int leftMax = nums[0];
        int globalMax = nums[0];
        int partitionIndex = 0;

        for (int i = 1; i < nums.length; i++) {
            globalMax = Math.max(globalMax, nums[i]);

            if (nums[i] < leftMax) {
                partitionIndex = i;
                leftMax = globalMax;
            }
        }

        return partitionIndex + 1;
    }
}

---

6. Dry Run Examples

Example 1

Input:

[5,0,3,8,6]

Step-by-step:

• leftMax = 5, globalMax = 5
• i=1: nums[1]=0 < leftMax → partitionIndex=1, leftMax=5
• i=2: nums[2]=3 < leftMax → partitionIndex=2, leftMax=5
• i=3: nums[3]=8 → update globalMax = 8
• i=4: nums[4]=6

Final:

partitionIndex + 1 = 3

Output:

3

---

Example 2

Input:

[1,1,1,0,6,12]

Trace:

• leftMax=1
• nums[1]=1
• nums[2]=1
• nums[3]=0 < leftMax → partitionIndex=3, leftMax=1
• nums[4]=6 globalMax=6
• nums[5]=12 globalMax=12

Output:

4

---

Example 3

Input:

[1,2,3]

First element always enough because always <= right

Output:

1

---

Example 4

Input:

[10,5,6,7,8,9]

nums[1]=5 < 10 → extend
nums[2]=6 < 10 → extend
…
nums[5]=9 < 10 → extend

Entire left must contain all elements

Output:

6

---

Example 5

Input:

[2,0,1]

nums[1]=0 < 2 → extend
nums[2]=1 < 2 → extend

Output:

3

---

7. Why This Solution Works

• leftMax ensures left side constraint enforced
• globalMax allows safe expansion of boundary
• minimal left achieved by updating only when necessary
• greedy correctness proven by monotonic partition rule
• avoids expensive min-right preprocessing

---

8. Common Mistakes

1. Trying to sort array (invalid because partition must be contiguous)
2. Precomputing right mins using extra arrays (works but uses O(N) space)
3. Confusing with two-pointer partitioning
4. Returning partition index instead of size
5. Forgetting left must be non-empty