Problems

# Rotate Array

## Problem

Rotate an array of `n` elements to the right by `k` steps.

### Example

For example, with `n = 7` and `k = 3`, the array `[1,2,3,4,5,6,7]` is rotated to `[5,6,7,1,2,3,4]`.

## Solution

If you rotate one step to the right each time and rotate k times (code below), you will get Time Limit Exceeded. Time complexity `O(k*n)`, Space complexity `O(1)`.

``````// !!! This will time out
k %= nums.size();
if (k == 0) return;
int i, j, tmp;
for (i = 0; i < k; i++) {
tmp = nums[nums.size()-1];
for (j = nums.size()-1; j > 0; j--) {
nums[j] = nums[j-1];
}
nums[0] = tmp;
}
``````

A better solution is to create a new array and fill each element right into the position. Time complexity `O(n)`, Space complexity `O(n)`.

``````k %= nums.size();
if (k == 0) return;
int i;
vector<int> tmp;
for (i = 0; i < nums.size(); i++) tmp.push_back(nums[i]);
for (i = 0; i < tmp.size(); i++) {
nums[(i+k)%nums.size()] = tmp[i];
}
``````

To further reduce space complexity, first reverse the whole array in place. Then reverse the first k elements, and also the rest n-k elements. Time complexity `O(n)`, Space complexity `O(1)`.

``````k %= nums.size();
if (k == 0) return;
int i, j, tmp;
for (i = 0, j = nums.size()-1; i < j; i++, j--) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
for (i = 0, j = k-1; i < j; i++, j--) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
for (i = k, j = nums.size()-1; i < j; i++, j--) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
``````