# Leetcode: Partition Array into Disjoint Intervals

Partition Array into Disjoint Intervals Similar Problems:

Given an array A, 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 1:

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

Example 2:

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

Note:

1. 2 <= A.length <= 30000
2. 0 <= A[i] <= 10^6
3. It is guaranteed there is at least one way to partition A as described.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/partition-array-into-disjoint-intervals
// Basic Ideas:
// max: maximum for the target left window
// global_max: maximum from the first element to the current one
//    If A[i] < max, we update max with global_max
// Complexity: Time O(n), Space O(1)
func partitionDisjoint(A []int) int {
max, global_max, res := A, A, 1
for i:= 1; i<len(A); i++ {
if A[i] < max {
max = global_max
res = i+1
} else {
if A[i] > global_max { global_max = A[i] }
}
}
return res
}
```

Share It, If You Like It.