package cn.fmachine.lintcode.easy;

import java.util.ArrayList;

/**
 * Given a rotated sorted array, recover it to sorted array in-place.
 * <p>
 * Have you met this question in a real interview? Yes
 * Clarification
 * What is rotated array?
 * <p>
 * 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]
 * Example
 * [4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
 * <p>
 * Challenge
 * In-place, O(1) extra space and O(n) time.
 * <p>
 * algorithm
 * Author: XIN MING
 * Date: 10/6/16
 */
public class RecoverRotatedSortedArray {
    /**
     * @param nums: The rotated sorted array
     * @return: void
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        int offset = -1;
        for (int i = 1; i < nums.size() - 1; i++) {
            if (nums.get(i) < nums.get(i - 1)) {
                offset = i - 1;
                break;
            }
        }
        if (offset == -1) return;

        reverse(nums, 0, offset);
        reverse(nums, offset + 1, nums.size() - 1);
        reverse(nums, 0, nums.size() - 1);
    }

    private void reverse(ArrayList<Integer> nums, int start, int end) {
        for (; start < end; start++, end--) {
            int temp = nums.get(start);
            nums.set(start, nums.get(end));
            nums.set(end, temp);
        }
    }
}
