> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/unsorted-array/partition-array.md).

# Partition Array

## Question 1 ([LI.31](http://www.lintcode.com/en/problem/partition-array/))

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

## Code

```java
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](http://www.lintcode.com/en/problem/partition-array-ii/))

> 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

```java
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++;
        }
    }
}
```