# [LeetCode 915. Partition Array into Disjoint Intervals ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3823/)
### Daily challenge Jul 22, 2021 (MEDIAN)

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

:::info
**Example 1:**
**Input:** nums = [5,0,3,8,6]
**utput:** 3
**Explanation:** left = [5,0,3], right = [8,6]
:::

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

:::warning
**Constraints:**
* 2 <= nums.length <= 30000
* 0 <= nums[i] <= 106
* It is guaranteed there is at least one way to partition nums as described.
:::

---

### Approach 1 : Two Pointer :bulb:
**`24 ms ( 91.51% )`** **`O(N)`**

將 `nums` 劃分為 `left part & right part` 兩部分，`left part` 中每個元素需**小於等於** `right part`。

* 使用兩個 `Pointer` ---> **`left & right`** 代表 `left & right part` 結束的 `index`。
* **`left_max`** 紀錄`left part` 的最大值。
* **`current_max`** 紀錄走過的最大值 ---> 可能成為下一個 `left_max` 。
* 判斷條件 :
> 1. **`nums[right] < nums[left]`** ( 劃分**錯誤** ---> `right part` 存在比 `left part` 小的 `element` ) :
> ---> `right` 以前的點應該歸為 `left part` ---> **`left = right`**，並更新 **`left_max`**。
> 2. **`nums[right] >= nums[left]`** ( 劃分**正確** ) :
> ---> 同時更新 **`current_max`**。
> 3. `right` 每次 `+1` 遍歷所有元素。
> 4. 最後回傳 **`left + 1`** ( 因為要求 `length of left part` )。
---
> **EXAMPLE :** `nums = [32, 57, 24, 19, 0, 24, 49, 67, 87, 87]`。
> :::spoiler 詳細過程
> * Initial state ---> **`left_max = nums[0] = 32`**，**`current_max = left_max = 32`**。
> 1. `57 > left_max`
> ---> `left_max = 32`，**`current_max = 57`**。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| L | R | | | | | | | | |
>
> 2. `24 < left_max` :x:
> ---> **`left_max = current_max = 57`**，`current_max = 57`。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| L | | R | | | | | | | |
>
> 3. `19 < left_max` :x:
> ---> **`left_max = current_max = 57`**，`current_max = 57`。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | L | R | | | | | | |
>
> 4. `0 < left_max` :x:
> ---> **`left_max = current_max = 57`**，`current_max = 57`。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | | L | R | | | | | |
>
> 5. `24 < left_max` :x:
> ---> **`left_max = current_max = 57`**，`current_max = 57`。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | | | L | R | | | | |
>
> 6. `49 < left_max` :x:
> ---> **`left_max = current_max = 57`**，`current_max = 57`。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | | | | L | R | | | |
>
> 7. `67 > left_max`
> ---> `left_max = 57`，**`current_max = 67`**。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | | | | | L | R | | |
>
> 8. `87 > left_max`
> ---> `left_max = 57`，**`current_max = 87`**。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | | | | | L | | R | |
>
> 9. `87 > left_max`
> ---> `left_max = 57`，**`current_max = 87`**。
>
>| 32 | 57 | 24 | 19 | 0 | 24 | 49 | 67 | 87 | 87 |
>|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
>| | | | | | | L | | | R |
>
> 10. 回傳 **`left + 1 = 7`**。

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int left = 0, right = 1;
        int left_max = nums[0];       // current max
        int current_max = nums[0];    // may be next left_max
        
        while(right < nums.size()){
            if(nums[right] < left_max){
                left = right;
                left_max = current_max;
            }    
            else    current_max = max(current_max, nums[right]);
            
            right++;
        }
        
        return left + 1;
    }
};