Recover Rotated Sorted Array

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

Have you met this question in a real interview? 

Yes

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]

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: void
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
       if(nums == null || nums.size() <= 1) return;
       int idx = 0;
       for(int i = 1; i < nums.size(); i++){
           if(nums.get(i-1) > nums.get(i)){
               idx = i;
           }
       }
       reverseNums(nums, 0, idx-1);
       reverseNums(nums, idx, nums.size()-1);
       reverseNums(nums, 0, nums.size()-1);
     
    }
   
    private void reverseNums(ArrayList<Integer> nums, int i, int j){
       
        while(i < j){
            int temp = nums.get(i);
            nums.set(i, nums.get(j));
            nums.set(j, temp);
            i++; j--;
        }
    }
}