Partition Array

Question 1 (LI.31)

Given an integer array nums and a pivot, partition the array.

Code

public int partitionArray(int[] nums, int pivot) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {
        // swap after cannot move anymore
        while (i <= j && nums[i] < pivot) {
            i++;
        }
        while (i <= j && nums[j] >= pivot) {
            j--;
        }
        // swap to keep the relative order
        if (i <= j) {
            swap(nums, i, j);
            i++;
            j--;                
        }
    }
    return i;
}

Question 2 (LI.625)

Partition the array into three parts, highBar.

Example

I: [4,3,4,1,2,3,1,2], 2, 3
O: [1,1 | 3,2,3,2 | 4,4]

Code

public void partition2(int[] nums, int lowBar, int highBar) {
    int left = 0, right = nums.length - 1;
    int i = 0;
    while (i < right) {
        if (nums[i] < lowBar) {
            swap(nums, i, left);
            left++;
            i++;
        } else if (nums[i] > highBar) {
            swap(nums, i, right);
            right--;
        } else {
            // middle section
            i++;
        }
    }
}