Lintcode 625. Partition Array II

Partition an unsorted integer array into three parts:

1. The front part < low
2. The middle part >= low & <= high
3. The tail part > high

Return any of the possible solutions.

Example

Example 1:

Input:
[4,3,4,1,2,3,1,2]
2
3
Output:
[1,1,2,3,2,3,4,4]
Explanation:
[1,1,2,2,3,3,4,4] is also a correct answer, but [1,2,1,2,3,3,4,4] is not

Example 2:

Input:
[3,2,1]
2
3
Output:
[1,2,3]

Challenge

1. Do it in place.
2. Do it in one pass (one loop).

Notice

low <= high in all testcases.

Code (Java):

public class Solution {
    /**
     * @param nums: an integer array
     * @param low: An integer
     * @param high: An integer
     * @return: nothing
     */
    public void partition2(int[] nums, int low, int high) {
        if (nums == null || nums.length == 0 || low > high) {
            return;
        }

        int pLow = 0;
        int pHigh = nums.length - 1;

        int i = 0;
        while (i <= pHigh) {
            if (nums[i] < low) {
                swap(nums, pLow, i);
                pLow++;
                i++;
            } else if (nums[i] > high) {
                swap(nums, pHigh, i);
                pHigh--;
            } else {
                i++;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}