Cyclically rotate an array

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}