[Rotate]Rotate Array

1. Example
n = 7 (array size)and k =3(rotate right steps)
a= [1,2,3,4,5,6,7]
becomes
1 step, a=[7, 1,2,3,4,5,6] (shifted 7 to the leftmost)
2 steps, a= [6,7, 1,2,3,4,5] (shifted 6 to the leftmost)
3 steps, a =[5,6,7,  1,2,3,4] (shifted 5 to the leftmost)

Thought 1: shift one element to the leftmost at a time,
Q1: how to shift to the leftmost?
A1:keep swapping backward from the end of the array
Time would be O(k*n),  space would be O(1)

Thought2: a =[5,6,7,     1,2,3,4], create a new array and assign the first three element from the end of the input array one by one until k (length to length-k+1) and assign the rest from the start of array (0 to length-K)
Time is O(n) for over all array, Space is O(n) for a new array

Thought3: Reverse technique, taking 3 reverse
Q1: what is reverse and how?
A1: [1,2,3] => [3,2,1] or [4,100,120,5]=>[5,100,120,4] and use swap between the first and the last
so rotate need 3 reverse
E.g., a= [1,2,3,4,5,6,7]
1st reverse idx 0 to n-k-1 [4,3,2,1   5,6,7]
2st reverse idx n-k to n-1 [4,3,2,1   7,6,5]
3st reverse idx 0 to n-1    [5,6,7,1,2,3,4]
Time:(3*n) , Space:O(1)

2. Implementation
// NOTE: k value 
// NOTE: overwrite the original array [in-place array overwrite]

// NOTE: validate the input of reverse

// Time:O(k*n), Space:O(1)
public void rotate (int[] nums, int k)
{
    // valid the input
    if ( nums== null || nums.length==0 )
    {
        throw new IllegaArgumentException("IllegalArgument");
    }
    // NOTE: k value
    if ( k  > nums.length)
    {
        k = k%nums.length;
    }
    if ( k == 0 )
    {
        return;
    }


    for (int i = 0 ; i < k ; i ++)
    {
          // NOTE: i >0 since j-1
          for (int j = nums.length -1 ;i>0; i--)
          {
              int temp = nums[j];
              nums[j] = nums[j-1];
              nums[j-1] = temp;
          }
    }
}

// Time:O(n) over array, Space:O(n) new array
public void rotate (int[] nums, int k)
{
     // valid the input
     if (nums == null || nums.length = 0)
     {
          throw new IllegalArgumentException("Illegal Argument");
     }
     if ( k > nums.length > 0)
     {
         k = k% nums.length;
     }
     if ( k == 0 )
     {
         return;
     }



     int[] res = new int[nums.length];
     for (int i = 0 ; i < k ; i ++)
     {
         res[i] = nums[nums.length-k  + i];// start from rotate element 1
     }
     for (int i = k ; i < res.length;i++)
     {
         res[i] = nums[i - k];
     }



     // NOTE: overwrite the original array [in-place array overwrite]
     System.arraycopy(res, 0, nums,0, nums.length);
}

// Time:O(n), Space:O(1)
public void rotate(int[] nums, int k)
{
     if (nums == null || nums.length == 0)
     {
          throw new IllegalArgumentException("illegal Argument");
     }
     if (k > nums.length )
     {
          k =  k% nums.length;
     }
     if (k ==0 )
     {
          return;
     }



     reverse(nums, 0, nums.length-k-1);// length-k is rotate start
     reverse(nums, nums.length -k, nums.length-1);
     reverse(nums, 0, nums.length-1);
}

public void reverse(int[] nums, int l, int r)
{
    // NOTE: validate the input of reverse
    if (nums == null || nums.length ==1 )
    {
        return;
    }



    while (l < r)
    {
         int temp = nums[l];
         nums[l] = nums[r];
         nums[r] = temp;
         l++;
         r--;
    }
}

3. Similar Ones
(M) Rotate List
(M) Reverse Words in a String II
[LinkedList] Reverse Linked List