Woodstock Blog

a tech blog for general algorithmic interview questions

[LintCode] Recover Rotated Sorted Array

Question

link

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--;
    }
}