### Question

Given a **rotated** sorted array, recover it to sorted array in-place.

**Example**

**[4, 5, 1, 2, 3]** -> **[1, 2, 3, 4, 5]**

**Challenge**

In-place, O(1) extra space and O(n) time.

**Clarification**

What is rotated array:

- For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

### Analysis

O(n) time and O(a) space is required.

Find the rotate position and rotate each half. After this:

**[4, 5, 1, 2, 3]** -> **[5, 4, 3, 2, 1]**

Then reverse it again. This solution is called “三步翻转法”, an extremely common interview algorithm. Similar questions are [LeetCode 151] Reverse Words in a String.

**Updated on Apr 11th, 2015**:

Thanks to the **nice little help from Shawn**, I found out that using **binary search** to find the rotation point is impossible, because of duplication. I wasn’t able to point this out previously, thus apologize to all!

### My code

```
public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
// write your code
if (nums == null || nums.size() <= 1) {
return;
}
int p = 1;
while (p < nums.size()) {
if (nums.get(p - 1) > nums.get(p)) {
break;
}
p++;
}
inPlaceRotate(nums, 0, p - 1);
inPlaceRotate(nums, p, nums.size() - 1);
inPlaceRotate(nums, 0, nums.size() - 1);
}
private void inPlaceRotate(ArrayList<Integer> nums, int left, int right) {
while (left < right) {
int temp = nums.get(left);
nums.set(left, nums.get(right));
nums.set(right, temp);
left++;
right--;
}
}
```