Cyclically Shift an Array by K Steps
Solve this Problemnums and an integer k, return the array after rotating it to the right by k positions — each element moves k spots to the right, wrapping around to the front when it runs past the end.
k may be larger than the array's length, so start by reducing it with k % nums.length before rotating.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
-10⁹ ≤ nums[i] ≤ 10⁹ - ◆
0 ≤ k ≤ 10⁵
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int[] rotateArray(int[] nums, int k) { |
| 3 | int n = nums.length; |
| 4 | int steps = k % n; |
| 5 | int[] result = nums.clone(); |
| 6 | reverse(result, 0, n - 1); |
| 7 | reverse(result, 0, steps - 1); |
| 8 | reverse(result, steps, n - 1); |
| 9 | return result; |
| 10 | } |
| 11 | |
| 12 | private void reverse(int[] arr, int lo, int hi) { |
| 13 | while (lo < hi) { |
| 14 | int tmp = arr[lo]; |
| 15 | arr[lo] = arr[hi]; |
| 16 | arr[hi] = tmp; |
| 17 | lo++; |
| 18 | hi--; |
| 19 | } |
| 20 | } |
| 21 | } |
| 22 |
522k = 2 is already less than n = 5, so steps stays 2. We'll reverse the whole array, then reverse it back in two chunks.
Approach & Solutions
Brute Force — Shift One Step at a Time
BruteRotate the array right by a single step — pop the last element off and insert it at the front — and repeat that k times (using k mod n to avoid redundant full loops). Simple to reason about, but doing k separate full-array shifts is wasteful for large k.
O(n · k)O(n)1class Solution {
2 public int[] rotateArray(int[] nums, int k) {
3 int n = nums.length;
4 int steps = k % n;
5 int[] result = nums.clone();
6 for (int s = 0; s < steps; s++) {
7 int last = result[n - 1];
8 for (int i = n - 1; i > 0; i--) {
9 result[i] = result[i - 1];
10 }
11 result[0] = last;
12 }
13 return result;
14 }
15}Better — Extra Array
BetterCompute steps = k % n, then for every index i, place nums[i] directly at its final rotated position (i + steps) % n in a brand-new array. This reaches the same O(n) time as the three-reversal trick without any reversing logic — but it needs a second array the size of the input, unlike the truly in-place reversal approach below.
O(n)O(n)1class Solution {
2 public int[] rotateArray(int[] nums, int k) {
3 int n = nums.length;
4 int steps = k % n;
5 int[] result = new int[n];
6 for (int i = 0; i < n; i++) {
7 result[(i + steps) % n] = nums[i];
8 }
9 return result;
10 }
11}Optimal — Three Reversals
OptimalReverse the entire array first. That flips both halves into backwards order, but the two "blocks" that should swap places are now next to each other in reverse. Reversing each of those two blocks individually un-reverses them locally while leaving them swapped globally — exactly a k-step rotation, done in one pass with no extra array.
O(n)O(1) extra1class Solution {
2 public int[] rotateArray(int[] nums, int k) {
3 int n = nums.length;
4 int steps = k % n;
5 int[] result = nums.clone();
6 reverse(result, 0, n - 1);
7 reverse(result, 0, steps - 1);
8 reverse(result, steps, n - 1);
9 return result;
10 }
11
12 private void reverse(int[] arr, int lo, int hi) {
13 while (lo < hi) {
14 int tmp = arr[lo];
15 arr[lo] = arr[hi];
16 arr[hi] = tmp;
17 lo++;
18 hi--;
19 }
20 }
21}