Cyclically rotate an array
Problem
Rotate the array to the right by one position: the last element moves to the front and every other element shifts one place right. The follow-up asks you to rotate by k positions in O(n) time and O(1) space.
Example 1
Input: [1, 2, 3, 4, 5] Output: [5, 1, 2, 3, 4]
Example 2
Input: [1, 2, 3, 4, 5], k = 2 Output: [4, 5, 1, 2, 3]
Also asked as: Write a program to cyclically rotate an array by one
Test cases
Case 1
Input: [1,2,3,4,5] Expected: [5,1,2,3,4]
Case 2
Input: [1,2] Expected: [2,1]
Case 3
Input: [1] Expected: [1]
View solutionHide solution2 approaches
1. Rotate by one (shift)
Time O(n)Space O(1)
Save the last element, shift everyone right by one, put it in front.
function rotateByOne(a) { const last = a[a.length - 1]; for (let i = a.length - 1; i > 0; i--) a[i] = a[i - 1]; a[0] = last; return a;}2. Rotate by k — reversal algorithm
Time O(n)Space O(1)
Reverse the whole array, then reverse the first k and the rest.
function rotate(a, k) { k %= a.length; const rev = (l, r) => { while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; } }; rev(0, a.length - 1); rev(0, k - 1); rev(k, a.length - 1); return a;}