Reference: LeetCode
Difficulty: Easy

My Post: Java 4 Solutions with Detailed Comments and Explanations (b-f, extra space, in-place)

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example: 

1
2
3
4
5
6
Input: [1,2,3,4,5,6,7] and 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]

Follow up:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with $O(1)$ extra space?

Analysis

Extra Space

The extra-space approach violates the requirement of the problem. The idea is simple. Find the start index after shifting and traverse the whole array starting from this index. Every time we visit an element, we put it into a new array.

1
2
3
4
5
0 1 2 3 4 5 6  k = 3, n = 7
1 2 3 4 5 6 7
        s
s goes through 5, 6, 7, 1, 2, 3, 4
5 6 7 1 2 3 4

Note: Before accessing the element at where the cursor points to, calculate cursor index modulo number of elements, which is (startIdx + i) % n.

1
2
3
4
5
6
7
8
9
10
11

public void rotate(int[] nums, int k) {
  int n = nums.length;
  k = k % n;
  int startIdx = n - k;
  int[] result = new int[nums.length];
  for (int i = 0; i < n; ++i) {
    result[i] = nums[(startIdx + i) % n];
  }
  System.arraycopy(result, 0, nums, 0, n);
}

Time: $O(N)$
Space: $O(N)$

Brute-Force (In-Place)

The brute-force solution just simulates the rotating process in a step-by-step manner. The outer loop indicates how many rotations we should do; the inner loop rotates each element from left to right.

1
2
3
4
5
6
0 1 2 3 4 5 6  k = 3, n = 7
1 2 3 4 5 6 7  prev = 7
7 1 2 3 4 5 6  prev = 6
6 7 1 2 3 4 5
// ...
5 6 7 1 2 3 4

As for the inner loop, prev starts by pointing the last element (eg. 7). Before it goes to its position (eg. index = 0), the original element (eg. 1) in that position should be stored in temp. Then we set prev as temp and process the next element (prev = 1).

1
2
3
4
5
6
7
8
9
10
11
12
13
public void rotate(int[] nums, int k) {
  int n = nums.length;
  k = k % n;
  for (int i = 0; i < k; ++i) { // rotate by k times
    // each time rotate all elements by one step, starting from the rihgtmost element
    int prev = nums[n - 1];
    for (int j = 0; j < n; ++j) {
      int temp = nums[j]; // backup
      nums[j] = prev;
      prev = temp;
    }
  }
}

We can also using the idea of shifting. We shift the first $n - 1$ elements by one before placing the last element in the beginning of the array.

Time: $O(N \times K)$
Space: $O(1)$

Shift Elements (In-Place)

Although we still process $k$-time rotations, at each time we just shift $(n - k)$ elements. Check the example below.

1
2
3
4
5
6
7
8
9
10
11
12
13
0 1 2 3 4 5 6  k = 3, n = 7
1 2 3 4 5 6 7  moveIdx points to 5, and 6, and 7
shift 1,2,3,4 right providing space for 5
  1 2 3 4 6 7
5   <-- place 5 here

shift 1,2,3,4 right providing space for 6
5   1 2 3 4 7
  6

shift 1,2,3,4 right providing space for 7
5 6   1 2 3 4
    7

Note: Use leftIdx to indicate where we put the element at. It also guides the shifting range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void rotate(int[] nums, int k) {
  int n = nums.length;
  k = k % n;
  int moveIdx = n - k;
  // move elements from moveIdx to the beginning
  for (int i = moveIdx, leftIdx = 0; i < n; ++i, ++leftIdx) {
    int num = nums[i];
    // move elements [0, moveIdx - 1] to the right by one
    for (int j = i - 1; j >= leftIdx; --j) {
      nums[j + 1] = nums[j];
    }
    nums[leftIdx] = num;
  }
}

Time: $O(k \times (N - k))$. In the worst case, it is bounded by $O(N^2)$.
Space: $O(1)$

Reverse (In-Place)

To achieve $O(N)$ time complexity, we can use the idea of reversing. Let’s verify the correctness by an example.

1
2
3
4
5
6
7
8
9
0 1 2 3 4 5 6  k = 3, n = 7
1 2 3 4 5 6 7
Reverse all elements
7 6 5 4 3 2 1
Reverse first k elements
5 6 7
Reverse last (n - k) elements
      1 2 3 4
5 6 7 1 2 3 4
  • Reverse all elements | $O(N)$
  • Reverse first $k$ elements | $O(k)$
  • Reverse last $(n - k)$ elements | $O(N - k)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void rotate(int[] nums, int k) {
  int n = nums.length;
  k = k % n;
  reverse(nums, 0, n - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, n - 1);
}

private void reverse(int[] nums, int lo, int hi) {
  int n = hi - lo + 1;
  for (int i = 0; i < n / 2; ++i) {
    swap(nums, lo + i, hi - i);
  }
}

private void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

Time: $O(N)$
Space: $O(1)$

Cyclic Replacements (In-Place)

Reference: LeetCode Solution