Reference: LeetCode
Difficulty: Easy
My Post: Java 4 Solutions with Detailed Comments and Explanations (bf, extra space, inplace)
Problem
Given an array, rotate the array to the right by
k
steps, wherek
is nonnegative.
Example:
1  Input: [1,2,3,4,5,6,7] and k = 3 
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
inplace
with $O(1)$ extra space?
Analysis
Extra Space
The extraspace 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  0 1 2 3 4 5 6 k = 3, n = 7 
Note: Before accessing the element at where the cursor points to, calculate cursor index
modulo number of elements
, which is (startIdx + i) % n
.
1 

Time: $O(N)$
Space: $O(N)$
BruteForce (InPlace)
The bruteforce solution just simulates the rotating process in a stepbystep manner. The outer loop indicates how many rotations we should do; the inner loop rotates each element from left to right.
1  0 1 2 3 4 5 6 k = 3, n = 7 
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  public void rotate(int[] nums, int k) { 
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 (InPlace)
Although we still process $k$time rotations, at each time we just shift $(n  k)$ elements. Check the example below.
1  0 1 2 3 4 5 6 k = 3, n = 7 
Note: Use leftIdx
to indicate where we put the element at. It also guides the shifting range.
1  public void rotate(int[] nums, int k) { 
Time: $O(k \times (N  k))$. In the worst case, it is bounded by $O(N^2)$.
Space: $O(1)$
Reverse (InPlace)
To achieve $O(N)$ time complexity, we can use the idea of reversing. Letâ€™s verify the correctness by an example.
1  0 1 2 3 4 5 6 k = 3, n = 7 
 Reverse all elements  $O(N)$
 Reverse first $k$ elements  $O(k)$
 Reverse last $(n  k)$ elements  $O(N  k)$
1  public void rotate(int[] nums, int k) { 
Time: $O(N)$
Space: $O(1)$
Cyclic Replacements (InPlace)
Reference: LeetCode Solution