Rotate Array

Problem Description

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. (Note that k may be greater than the size of the array and our solution must be in-place)

Input: nums = [1,2,3,4,5,6,7],  k = 3
Output: [5,6,7,1,2,3,4]

Step by step explanation:

• Rotate 1 steps to right : [7, 1, 2, 3, 4, 5, 6]
• Rotate 2 steps to right : [6, 7, 1, 2, 3, 4, 5]
• Rotate 3 steps to right : [5, 6, 7, 1, 2, 3, 4]

Intuition

Before diving into the discussion, there is an edge case that we should cover first.
Full rotation can happen many times since k can be greater than size of array.
Considering input array, rotating 3 times and 10 times returns exactly the same results, we'll keep this in mind.

Brute force approach with O(n2) complexity for this problem:

• implement a function that rotates one step to right
• call that function k times to get the result

public void rotateArray(int[] arr, int k){
  k = k % arr.length; //by applying modulus, we'll get the same result with less than k rotation 
  for(int i=0; i<k; i++){
    rotateRight(arr);
  }
}

public void rotateRight(int[] arr){
  int temp = arr[arr.length-1];
  for(int i=arr.length-1; i>=1; i--){
    arr[i] = arr[i-1];
  }
  arr[0] = temp;
}

Optimized approach with reversing strategy with O(n) complexity, explained as follows:

• reverse the entire array -> [7,6,5,4,3,2,1]
• reverse the first part of the array (from 0 to k-1) -> [5,6,7,4,3,2,1]
• reverse the remaining part of the array (from k to arr.length - 1) -> [5,6,7,1,2,3,4]

public void rotateArray(int[] nums, int k) {
  k %= nums.length;
  reverseArr(nums,0,nums.length-1);
  reverseArr(nums,0,k-1);
  reverseArr(nums,k,nums.length-1);
}

public void reverseArr(int[] arr, int start, int end){
  while(start < end){
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;end--;
  }
}