LeetCode 915 - Partition Array into Disjoint Intervals

https://leetcode.com/problems/partition-array-into-disjoint-intervals/

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]

X.
https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175907/O(n)-One-Pass-Solution

endIndex is the leftmost index of left part
maxIndex is max number's we encountered so far
maxCurrIndex is the max number's index in the left part

    public int PartitionDisjoint(int[] A) {
        
        int maxCurrIndex = 0;
        int maxIndex = 0;
        int endIndex = 0;
        
        
        for(int i=1;i<A.Length;i++){
            
            if(A[i] < A[maxCurrIndex]){
                maxCurrIndex = maxIndex;
                endIndex = i;
            }else if(A[i] > A[maxIndex]){
                maxIndex = i;
            }
            
        }
        return endIndex+1;
        
    }




by maintaining two variables prevMax & curMax

https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/177339/Java-simple-solution-O(n)-time-and-O(1)-space-by-maintaining-two-variables-prevMax-and-curMax

（1）开辟两个变量leftMax， rightMax 分别表示分割线左边区间的最大值，以及当前数组的最大值。然后，从左向右扫描数组。

（2）如果扫描的当前值小于leftMax，很显然此时的分割线需要更新，因为右区间所有值都应该大于左区间的所有值。在更新分割线res时，同时也要更新leftMax，获取左区间的最大值。并且重置 rightMax 。

（3）如果扫描的当前值大于或等于 leftMax，就接着判断与 rightMax 的大小关系，如果大于 rightMax ，就更新 rightMax 。直接到结束，就可以得出结果。

https://zxi.mytechroad.com/blog/greedy/leetcode-915-partition-array-into-disjoint-intervals/

  int partitionDisjoint(vector<int>& A) {    

    int left_max = A[0];

    int cur_max = A[0];

    int left_len = 1;

    for (int i = 1; i < A.size(); ++i) {

      if (A[i] < left_max) {

        left_max = cur_max;

        left_len = i + 1;        

      } else {

        cur_max = max(cur_max, A[i]);

      }

    }

    return left_len;

  }

X. O(1) space
https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175945/Java-one-pass-7-lines

public int partitionDisjoint(int[] a) {
        int localMax = a[0], partitionIdx = 0, max = localMax;
        for (int i = 1; i < a.length; i++)
            if (localMax > a[i]) {
                localMax = max;
                partitionIdx = i;
            } else max = Math.max(max, a[i]);
        return partitionIdx + 1;
    }

public int partitionDisjoint(int[] A) {

  int[] mins = new int[A.length];

  mins[A.length - 1] = A[A.length - 1];

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

    mins[i] = Math.min(A[i], mins[i + 1]);

  }

  int maxValue = A[0];

  for (int i = 1; i < A.length; i++) {

    if (maxValue <= mins[i])

      return i;

    else

      maxValue = Math.max(maxValue, A[i]);

  }

  return A.length;

}

https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175849/C%2B%2BJavaPython-Straight-Forward

B[i] stands for the minimum value in subarray A[i], A[i+1], ..., A[n-1]
pmax stands for the prefix maximum of i first values in A.
return the smallest that i that pmax <= B[i]

    public int partitionDisjoint(int[] A) {
        int n = A.length, pmax = 0, B[] = new int[n];
        B[n - 1] = A[n - 1];
        for (int i = n - 2; i > 0; --i)
            B[i] = Math.min(A[i], B[i + 1]);
        for (int i = 1; i < n; ++i) {
            pmax = Math.max(pmax, A[i - 1]);
            if (pmax <= B[i]) return i;
        }
        return n;
    }

Approach 1: Next Array

Instead of checking whether all(L <= R for L in left for R in right), let's check whether max(left) <= min(right).

Algorithm

Let's try to find max(left) for subarrays left = A[:1], left = A[:2], left = A[:3], ... etc. Specifically, maxleft[i] will be the maximum of subarray A[:i]. They are related to each other: max(A[:4]) = max(max(A[:3]), A[3]), so maxleft[4] = max(maxleft[3], A[3]).

Similarly, min(right) for every possible right can be found in linear time.

After we have a way to query max(left) and min(right) quickly, the solution is straightforward.

  public int partitionDisjoint(int[] A) {

    int N = A.length;

    int[] maxleft = new int[N];

    int[] minright = new int[N];

    int m = A[0];

    for (int i = 0; i < N; ++i) {

      m = Math.max(m, A[i]);

      maxleft[i] = m;

    }

    m = A[N - 1];

    for (int i = N - 1; i >= 0; --i) {

      m = Math.min(m, A[i]);

      minright[i] = m;

    }

    for (int i = 1; i < N; ++i)

      if (maxleft[i - 1] <= minright[i])

        return i;

    throw null;

  }

X. https://zxi.mytechroad.com/blog/greedy/leetcode-915-partition-array-into-disjoint-intervals/

  int partitionDisjoint(vector<int>& A) {

    multiset<int> s(begin(A) + 1, end(A));

    int left_max = A[0];

    for (int i = 1; i < A.size(); ++i) {      

      if (*begin(s) >= left_max) return i;

      s.erase(s.equal_range(A[i]).first);

      left_max = max(left_max, A[i]);      

    }

    return -1;

  }