Rotate Array to the right by k times.

ArrayRotation.java

/* File:    ArrayRotation.java
 * Created: 11/19/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

//=======================================================================================

/**
 * @author Sabbir Manandhar [email protected]
 * @version 1.0
 */
public class ArrayRotation {

  //-------------------------------------------------------------------------------------
  //------------- METHOD 1 --------------------------------------------------------------
  
  /**
   * Rotation method that uses an auxiliary array to store the result
   * of rotation. Once the rotation is done, each element is copied to
   * the original array.
   *
   * The method requires O(n) time and O(n) space.
   *
   * @param nums input array to rotate.
   * @param k number of times to ratate the array.
   */
  public void rotate(int[] nums, int k) {
    int N = nums.length;
    k = k % N;
    if (k == 0 || N < 2) return;

    int[] auxiliary = new int[N];
    for (int i = 0; i < k; i++) {
      int idx = N - 1 - i;
      int temp = nums[idx];
      while (idx - k >= 0) {
        auxiliary[idx] = nums[idx - k]; // push element from left to right
        idx -= k;
      }
      auxiliary[k - 1 - i] = temp; // bring element in the end section to front
    }

    for (int i = 0; i < N; i++) {
      nums[i] = auxiliary[i];
    }
  } // rotate

  //-------------------------------------------------------------------------------------
  //------------- METHOD 2 --------------------------------------------------------------

  /**
   * Rotation method that uses only a partial auxiliary array of size k.
   * Rotation mechanism is similar to first method difference being the beginning (n-k)
   * elements are rotated in place, only the last k elements are rotated and saved in
   * auxiliary array. Once the rotation is done, result is copied the be beginning of
   * original array.
   *
   * This method requires O(n) Time and O(k) space   *
   *
   * @param nums input array to rotate.
   * @param k number of times to ratate the array.
   */
  public void rotate2(int[] nums, int k) {
    k = k % nums.length;
    if (k == 0) return;
    int N = nums.length;
    int[] prefix = new int[k];
    for(int i = 0; i < k; i++) {
      int idx = N - 1 - i;
      int temp = nums[idx];
      while (idx - k >= 0) {
        //if (idx - k > 0) continue;
        nums[idx] = nums[idx - k]; // push element from left to right
        idx -= k;
      }
      prefix[k-1-i] = temp; // elements which cannot be pushed right. Save in prefix array
    }

    for (int i = 0; i < k; i++) {
      nums[i] = prefix[i]; // save elements from prefix array to original array
    }
  } // rotate2

  //-------------------------------------------------------------------------------------
  //------------- METHOD 3 --------------------------------------------------------------

  /**
   * This method first reverses first N - k and last k elements separately.
   * Finally reverse the whole array to give the required output array.
   *
   * This method requires O(n) time and O(1) space.
   *
   * @param nums input array to reverse.
   * @param k number of times to rotate the intput.
   */
  public void rotate3(int[] nums, int k) {
    k = k % nums.length;
    if (k == 0 || nums.length < 2) return;

    int N = nums.length;
    reverse(nums, 0, N - k);
    reverse(nums, N - k, N);
    reverse(nums, 0, N);
  } // rotate3

  //-------------------------------------------------------------------------------------

  /**
   * Reverses the array from index start (inclusive) to index end (exclusive)
   * @param nums input array
   * @param start start index
   * @param end end index
   */
  private void reverse(int[] nums, int start, int end) {
    while (start < end) {
      swap(nums, start, end-1);
      start++;
      end--;
    }
  } // reverse

  //-------------------------------------------------------------------------------------

  /**
   * Swaps two elements in an array at index i and j.
   * @param nums input array
   * @param i index i
   * @param j index j
   */
  private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  } // swap

} // ArrayRotation