Reference: LeetCode
Difficulty: Easy

Problem

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

Example:

• 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.

Note: Before accessing the element at where the cursor points to, calculate cursor index modulo number of elements, which is (startIdx + i) % 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.

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).

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.

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

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.

• Reverse all elements | $O(N)$
• Reverse first $k$ elements | $O(k)$
• Reverse last $(n - k)$ elements | $O(N - k)$

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

Cyclic Replacements (In-Place)

Reference: LeetCode Solution

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.