Given an array A
, partition it into two (contiguous) subarrays left
and right
so that:
<li>Every element in <code>left</code> is less than or equal to every element in <code>right</code>.</li>
<li><code>left</code> and <code>right</code> are non-empty.</li>
<li><code>left</code> has the smallest possible size.</li>
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:
<li><code>2 <= A.length <= 30000</code></li>
<li><code>0 <= A[i] <= 10^6</code></li>
<li>It is guaranteed there is at least one way to partition <code>A</code> as described.</li>