# [LintCode] Recover Rotated Sorted Array

### 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) {
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--;
}
}
``````