# Question

Formatted question description: https://leetcode.ca/all/189.html

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]


Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

# Algorithm

O(1) extra space.

Similar to the method of flipping characters, the idea is to

1. flip the first n-k numbers first,
2. then flip the last k numbers,
3. and finally flip the entire array.

Proces as below:

[1,2,3,4, 5,6,7] => [4,3,2,1, 5,6,7]

[4,3,2,1, 5,6,7] => [4,3,2,1, 7,6,5]

[4,3,2,1, 7,6,5] => [5,6,7, 1,2,3,4]


Easier implemetatioin is:

1. and finally flip the entire array first,
2. then flip the first k numbers,
3. flip the last n-k numbers

Proces as below:

[1,2,3,4, 5,6,7] => [7,6,5, 4,3,2,1]

[7,6,5, 4,3,2,1] => [5,6,7, 4,3,2,1]

[5,6,7, 4,3,2,1] => [5,6,7, 1,2,3,4]


# Code

• import org.apache.commons.lang3.ArrayUtils;

public class Rotate_Array {

class Solution {
public void rotate(int[] nums, int k) {
if (nums.length == 0 || (k %= nums.length) == 0) {
return;
}

int n = nums.length;

// [1,2,3,4,5,6,7] => [4,3,2,1,5,6,7]
ArrayUtils.reverse(nums, 0, n - k); // @note: org.apache.commons.lang3.ArrayUtils

// [4,3,2,1,5,6,7] => [4,3,2,1,7,6,5]
ArrayUtils.reverse(nums, n - k, nums.length);

// [4,3,2,1,7,6,5] => [5,6,7,1,2,3,4]
ArrayUtils.reverse(nums, 0, nums.length);
}
}

class Solution_kTimesAllItemsMoving {
public void rotate(int[] nums, int k) {

while ( k > 0) {
k--;

int tmp = nums[nums.length - 1]; // last one
for (int i = nums.length - 1; i >= 1; i--) {
nums[i] = nums[i - 1];
}

nums[0] = tmp;
}
}
}
}

############

class Solution {
public void rotate(int[] nums, int k) {
if (nums == null) {
return;
}
int n = nums.length;
k %= n;
if (n < 2 || k == 0) {
return;
}

rotate(nums, 0, n - 1);
rotate(nums, 0, k - 1);
rotate(nums, k, n - 1);
}

private void rotate(int[] nums, int i, int j) {
while (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
++i;
--j;
}
}
}

• // OJ: https://leetcode.com/problems/rotate-array/
// Time: O(N)
// Space: O(K)
class Solution {
public:
void rotate(vector<int>& A, int k) {
int N = A.size();
k %= N;
if (k == 0) return;
vector<int> tmp(k);
for (int i = 0; i < k; ++i) tmp[i] = A[N + i - k];
for (int i = N - k - 1; i >= 0; --i) A[i + k] = A[i];
for (int i = 0; i < k; ++i) A[i] = tmp[i];
}
};

• class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
if n < 2 or k == 0:
return
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]

############

class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
if len(nums) == 0 or k == 0:
return

def reverse(start, end, s):
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1

n = len(nums) - 1
k = k % len(nums)
reverse(0, n - k, nums)
reverse(n - k + 1, n, nums)
reverse(0, n, nums)


• func rotate(nums []int, k int) {
n := len(nums)
k %= n

reverse(nums, 0, n-1)
reverse(nums, 0, k-1)
reverse(nums, k, n-1)
}

func reverse(nums []int, i, j int) {
for i < j {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}


• /**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
k %= nums.length;
nums.splice(0, 0, ...nums.splice(-k, k));
};


• using System;

public class Solution {
public void Rotate(int[] nums, int k) {
if (nums.Length == 0 || k % nums.Length == 0) return;
k = k % nums.Length;
Algo2(nums, k);
}

private void Algo1(int[] nums, int k)
{
var copy = new int[nums.Length];
Array.Copy(nums, copy, nums.Length);
var j = nums.Length - k;
for (var i = 0; i < nums.Length; ++i)
{
if (j == nums.Length) j = 0;
nums[i] = copy[j];
++j;
}
}

private void Algo2(int[] nums, int k)
{
var gcd = Gcd(nums.Length, k);
var count = nums.Length / gcd;
for (var i = 0; i < gcd; ++i)
{
var p = i;
var first = nums[p];
for (var j = 0; j + 1 < count; ++j)
{
var q = p - k;
if (q < 0) q += nums.Length;
nums[p] = nums[q];
p = q;
}
nums[i + k] = first;
}
}

private int Gcd(int m, int n)
{
while (n > 0)
{
var x = m % n;
m = n;
n = x;
}
return m;
}
}

• impl Solution {
pub fn rotate(nums: &mut Vec<i32>, k: i32) {
let n = nums.len();
let k = k as usize % n;
if n == 1 || k == 0 {
return;
}

nums.reverse();
nums[..k].reverse();
nums[k..].reverse();
}
}


• /**
Do not return anything, modify nums in-place instead.
*/
function rotate(nums: number[], k: number): void {
const n: number = nums.length;
k %= n;
const reverse = (i: number, j: number): void => {
for (; i < j; ++i, --j) {
const t: number = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
};
reverse(0, n - 1);
reverse(0, k - 1);
reverse(k, n - 1);
}