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[1] to nums[0], nums[2] to nums[1]... 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[0], nums[6])
nums = [7, 2, 3, 4, 5, 6, 1]
start++
start = 1
end--
end = 5
Step 6: while start < end
1 < 5
true
swap(nums[1], nums[5])
nums = [7, 6, 3, 4, 5, 2, 1]
start++
start = 2
end--
end = 4
Step 7: while start < end
2 < 4
true
swap(nums[2], nums[4])
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[0], nums[2])
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[3], nums[6])
nums = [5, 6, 7, 1, 3, 2, 4]
start++
start = 4
end--
end = 5
Step 14: while start < end
4 < 5
true
swap(nums[4], nums[5])
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].
Top comments (0)