 # LeetCode - Rotate Array

### Problem statement

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

Problem statement taken from: https://leetcode.com/problems/rotate-array/.

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 <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5``````

### Explanation

#### Brute force solution

The brute force approach is to create a temporary(temp) array and store the first k elements in the temp array. We then shift the rest of the array by k places and append back the tmp array to the original array.

The flow will look as below:

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

1) Store the first k elements in a temp array
temp[] = [1, 2]

2) Shift rest of the nums[]
nums[] = [3, 4, 5, 6, 7, 6, 7]

3) Store back the k elements
nums[] = [3, 4, 5, 6, 7, 1, 2]``````

The time complexity of the above approach is O(N) and space complexity is O(k).

#### Rotate one by one

If we want to avoid using extra space, we can rotate the array elements one by one.

We store the first element of the array in temp variable and shift nums to nums, nums to nums... till the last element nums[n - 1] is shifted to nums[n - 2].

We repeat the above procedure k times.

The time complexity of the above approach is O(N*k) and space complexity if O(1).

#### Reversing an array

The problem can be solved in O(N) time by reversing array in parts. We consider array in two parts part1 = nums[0..k - 1] and part2 = nums[k..n - 1].

We reverse the elements present in the part1 array. We then reverse the part2 array elements. In the end, we reverse the entire array.

Let's check the algorithm to see how this solution works.

``````// rotate(nums, k)
- set n = nums.size()

- return if n == 1 or k == 0

- update k = k % n
This is done when k is greater than n.
eg n = 8, k = 12
k = k % n
= 12 % 8
= 4

- call reverseArray(nums, 0, n - 1)
- call reverseArray(nums, 0, k - 1)
- call reverseArray(nums, k, n - 1)

// reverseArray(nums, start, end)
- while start < end
- swap(nums[start], nums[end])
- start++
- end--``````

Let's check out our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
void reverseArray(vector<int>& nums, int start, int end) {
while(start < end) {
std::swap(nums[start], nums[end]);
start++;
end--;
}
}

void rotate(vector<int>& nums, int k) {
int n = nums.size();
if(n == 1 || k == 0) {
return;
}

k = k % n;
reverseArray(nums, 0, n - 1);
reverseArray(nums, 0, k - 1);
reverseArray(nums, k, n - 1);
}
};``````

#### Golang solution

``````func reverseArray(nums []int, start, end int) {
for start < end {
tmp := nums[start]
nums[start] = nums[end]
nums[end] = tmp
start++
end--
}
}

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

if n == 1 || k == 0 {
return
}

k = k % n

reverseArray(nums, 0, n - 1)
reverseArray(nums, 0, k - 1)
reverseArray(nums, k, n - 1)
}``````

#### Javascript solution

``````var reverseArray = function(nums, start, end) {
while(start < end) {
let tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
start++;
end--;
}
}

var rotate = function(nums, k) {
let n = nums.length;

if( n == 1 || k == 0 ) {
return;
}

k = k % n;
reverseArray(nums, 0, n - 1);
reverseArray(nums, 0, k - 1);
reverseArray(nums, k, n - 1);
};``````

Let's dry-run our algorithm to see how the solution works.

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

// rotate function
Step 1: n = nums.size()
= 7

Step 2: n == 1 || k == 0
7 == 1 || 3 == 0
false

Step 3: k = k % n
= 3 % 7
= 3

Step 4: reverseArray(nums, 0, n - 1)
reverseArray(nums, 0, 6)

// reverseArray(nums, start, end)
Step 5: while start < end
0 < 6
true

swap(nums, nums)
nums = [7, 2, 3, 4, 5, 6, 1]

start++
start = 1
end--
end = 5

Step 6: while start < end
1 < 5
true

swap(nums, nums)
nums = [7, 6, 3, 4, 5, 2, 1]

start++
start = 2
end--
end = 4

Step 7: while start < end
2 < 4
true

swap(nums, nums)
nums = [7, 6, 5, 4, 3, 2, 1]

start++
start = 3
end--
end = 3

Step 8: while start < end
3 < 3
false

// rotate function
Step 9: reverseArray(nums, 0, k - 1)
reverseArray(nums, 0, 2)

// reverseArray(nums, start, end)
Step 10: while start < end
0 < 2
true

swap(nums, nums)
nums = [5, 6, 7, 4, 3, 2, 1]

start++
start = 1
end--
end = 1

Step 11: while start < end
1 < 1
false

// rotate function
Step 12: reverseArray(nums, k, n - 1)
reverseArray(nums, 3, 6)

// reverseArray(nums, start, end)
Step 13: while start < end
3 < 6
true

swap(nums, nums)
nums = [5, 6, 7, 1, 3, 2, 4]

start++
start = 4
end--
end = 5

Step 14: while start < end
4 < 5
true

swap(nums, nums)
nums = [5, 6, 7, 1, 2, 3, 4]

start++
start = 5
end--
end = 4

Step 15: while start < end
5 < 4
false

// rotate function
no more steps to execute

We return the final array as [5, 6, 7, 1, 2, 3, 4].``````