# 189. Rotate Array

Description:

https://leetcode.com/problems/rotate-array/#/description

Algorithm:

Solution1: shift for k times

Solution2: use new vector. Initialize the new vector and reEvaluate the elements. The new offset = k % n; The new index = (i + n – offset) % n;

Solution3: use new vector. Push_back the new element one buy one. The new offset = n – k % n; The new index = (i + offset) % n;

Code:
``` ```

```#ifdef Solution1 class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); int offset = k % n; int tmp; if (offset < n / 2) for (int j = 0; j < offset; j++) { tmp = nums[n - 1]; for (int i = 0; i < nums.size();i++) { swap(nums[i], tmp); } } else for (int j = 0; j < n - offset; j++) { tmp = nums[0]; for (int i = nums.size() - 1; i >= 0;i--) { swap(nums[i], tmp); } } } }; #endif #ifdef Solution2 class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); vector<int> result = vector<int>(n, 0); int offset = k % n; for (int i = 0; i < nums.size();i++) { result[i] = nums[(i + n - offset) % n]; }nums = result; } }; #endif #ifdef Solution3 class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); int offset = n - k % n; vector<int> result; for (int i = 0; i < nums.size();i++) result.push_back(nums[(i + offset) % n]); nums = result; } }; #endif```

` `

Timing & Space:

• Solution1:
• Time: Worst: O(n * n/2), Best O(n), Avg O(n * n/4)
• Space: O(1)
• Solution2:
• Time: O(n)
• Space: O(n)
• Solution3:
• Time: O(n)
• Space: O(n)