[Java] Disjoint array partition

Given array of positive integers including zeros and duplicates, partition it in portions left and right such that every element in left is smaller than every element in right. Keep left as small as possible.

Example:

1,2,3 partition 1 - 2,3

3,2,1 partition 3,2,1 - empty

1,1,0,3,2 partition 1,1,0 - 3,2

1,1,3,2 partition 1 - 1,3,2

Looking at our examples, we can solve this in O(N) time and space by keeping track of the following information:

• minimum so far of all elements from right to left
• maximum so far of all elements from left to right

This is because we can notice that for each position from left to right we want to break there (and therefore generate the smallest partition) only if max at that position is less than or equal to min at the next position. 

In that case, every element BEFORE us (including us) will be less than or equal to every element AFTER us, satisfying the given condition.

We can improve slightly on space by noticing we don't need to remember max values, but only need the last one, so we can replace the max array with a variable.

We still need the min array though, for example: 

5,0,3,8,6

if we tracked only 0 as min, we would break at the end of the array since max until there is never less than 0.

By checking against the min value at the next position though, we break on 3, which is the correct answer. 

You can check my implementation of disjointPartition on my Gist along with some tests in DisjointPartitionJTests.