# 189 Rotate Array

Rotate an array ofnelements to the right byksteps.
For example, withn= 7 andk= 3, the array`[1,2,3,4,5,6,7]`is rotated to`[5,6,7,1,2,3,4]`.
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Solution 1 (Extra Space, O(n)): Hash to the location in the array the corresponds with its its rotated position.
void rotate(vector<int>& nums, int k)
{
vector<int> r_nums(nums.size());
for (int i = 0; i < nums.size(); i++) {
int rotate_hash = (i + k) % nums.size();
r_nums[rotate_hash] = nums[i];
}
nums = r_nums;
}
int main()
{
vector<int> nums = { 1,2,3,4,5,6,7 };
rotate(nums, 3);
print(nums);
}
Solution 2 (Constant Space, O(n)): Reverse the array entirely, and the reverse two segments divided at k.
Example:
Input
nums: 1 2 3 4 5 6 7
k : 3
rev : 7 6 5 4 3 2 1
rev(0, k) : 5 6 7 4 3 2 1
rev(k, end) : 5 6 7 1 2 3 4
void rotate(vector<int>& nums, int k)
{
k = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
int main()
{
vector<int> nums = { 1,2,3,4,5,6,7 };
rotate(nums, 3);
print(nums);
}