SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Rotate an Array By K Visualizer

Reverse the whole array, then reverse the first k values, then reverse the rest. The last k values end up in front, each part in its original order.

Start the Rotate an Array By K simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. k = 3 % 7 = 3. [1, 2, 3, 4, 5, 6, 7]
  2. Reverse the whole array: indexes 0 to 6.
  3. Swap 1 and 7. [7, 2, 3, 4, 5, 6, 1]
  4. Swap 2 and 6. [7, 6, 3, 4, 5, 2, 1]
  5. Swap 3 and 5. [7, 6, 5, 4, 3, 2, 1]
  6. Reverse the first 3: indexes 0 to 2.
  7. Swap 7 and 5. [5, 6, 7, 4, 3, 2, 1]
  8. Reverse the other 4: indexes 3 to 6.
  9. Swap 4 and 1. [5, 6, 7, 1, 3, 2, 4]
  10. Swap 3 and 2. [5, 6, 7, 1, 2, 3, 4]
  11. Done. Every value moved 3 to the right: 5, 6, 7, 1, 2, 3, 4.

Try it with your own input →

Rotate an array by k in Java, Python, C++, C and JavaScript

void rotate(int[] a, int k) {
  k %= a.length;
  reverse(a, 0, a.length - 1);
  reverse(a, 0, k - 1);
  reverse(a, k, a.length - 1);
}
def reverse(a, i, j):
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1; j -= 1

def rotate(a, k):
    k %= len(a)
    reverse(a, 0, len(a) - 1)
    reverse(a, 0, k - 1)
    reverse(a, k, len(a) - 1)
void rotate(vector<int>& a, int k) {
  k %= a.size();
  reverse(a.begin(), a.end());
  reverse(a.begin(), a.begin() + k);
  reverse(a.begin() + k, a.end());
}
void reverse(int a[], int i, int j) {
  while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
}
void rotate(int a[], int n, int k) {
  k %= n;
  reverse(a, 0, n - 1);
  reverse(a, 0, k - 1);
  reverse(a, k, n - 1);
}
function reverse(a, i, j) {
  while (i < j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
}
function rotate(a, k) {
  k %= a.length;
  reverse(a, 0, a.length - 1);
  reverse(a, 0, k - 1);
  reverse(a, k, a.length - 1);
}

In an interview

LeetCode 189, Rotate Array: move every value k places to the right, wrapping around, in place.

Do k %= n first: rotating by n changes nothing, and k can be bigger than n. Copying into a new array is O(n) space; the three reversals are O(1).

More patterns