Question

link

Given an array “nums” of integers and an int “k”, Partition the array (i.e move the elements in “nums”) such that,

1. All elements < k are moved to the left
2. All elements >= k are moved to the right

Return the partitioning Index, i.e the first index “i” nums[i] >= k.

Example: If nums=[3,2,2,1] and k=2, a valid answer is 1.

Analysis

The solution is to keep swapping elements. It confuses me for a while, until I realize the swapping mechanism is actually not difficult.

There’s another question on leetcode “Sort Color”, which is similar to this question (just partition twice).

Code

public int partitionArray(ArrayList<Integer> nums, int k) {
    //write your code here
    ArrayList<Integer> ans = new ArrayList<Integer>();
    if (nums == null || nums.size() == 0) {
        return ans;
    }
    int len = nums.size();
    int left = 0;
    int right = len - 1;
    while (left < right) {
        while (left < len && nums.get(left) < k) {
            left++;
        }
        while (right >= 0 && nums.get(right) >= k) {
            right--;
        }
        if (left > right) {
            break;
        } else {
            // swap 2 elements
            int temp = nums.get(left);
            nums.set(left, nums.get(right));
            nums.set(right, temp);
            left++;
            right--;
        }
    }
    // now return the correct value
    if (left == len) {
        return len;
    } else {
        return left;
    }
}