> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/phone-interview-i/chapter1.md).

# 31.Partition Array

## 1.Description(Medium)

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*.

### Notice

You should do really partition in array\_nums\_instead of just counting the numbers of integers smaller than k.

If all elements in*nums\_are smaller than\_k*, then return*nums.length*

**Example**

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

[**Challenge**](https://www.lintcode.com/en/problem/partition-array/#challenge)

Can you partition the array in-place and in O(n)?

[**Tags**](https://www.lintcode.com/en/problem/partition-array/#tags)

[Sort](https://www.lintcode.com/tag/sort/) [Two Pointers](https://www.lintcode.com/tag/two-pointers/) [Array](https://www.lintcode.com/tag/array/)

## 2.Code

```
public int partitionArray(int[] nums, int k) {
       if(nums==null || nums.length==0){
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            //注意这两个while里面都要加上ledt<=right 否则会出现java.lang.ArrayIndexOutOfBoundsException
            while(left<=right && nums[left]<k){
                left++;
            }
            while(left<=right && nums[right]>=k){
                right--;
            }
            if(left<=right){
                int temp=nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
                left++;
                right--;
            }
        }
        return left;
    }
```