Partition Array

Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:

• All elements < k are moved to the left
• All elements >= k are moved to the right

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

Corner cases:
k is not in the array and it is larger/ smaller than all the numbers in the array
It can be taken care of by or algorithm.
We manipulate to pointers moving towards each other. We make sure that every number before index left is [smaller] than our target and every number after index right is [larger or equal to] our target.
Two base cases are like
index      0          1           2
              left                   right

index      0          1           2           3
                         left       right

We can't stop when left == right because we still need to check the middle number.

public class Solution {
/**
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
   //write your code here
   if (nums == null || nums.length == 0) return 0;
   int l = 0;
   int r = nums.length - 1;
   while (l <= r) {
       while (l <= r && nums[l] < k) l++;
       while (l <= r && nums[r] >= k) r--;
       if (l <= r) {
           swap(nums, l, r);
           l++;
           r--;
       }
   }
   return l;
    }
   
    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) return;
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}