Question:
Given an array, rotate the array to the right by k steps, where k is non-negative.Example 1:Input: nums = [1,2,3,4,5,6,7], 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]Example 2:Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105Follow up:Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.Could you do it in-place with O(1) extra space?
When first looking at the question, I quickly came up with the idea of doing in-place updating, just as reversing an array. Unlike reverse or shift an array by one slot, the problem here to solve is how to memorize a subset of numbers where overwriting with new values. For example 1, it’s easy to let 5,6,7 to replace 1,2,3, but you need somewhere to store 1,2,3, as the old slots are taken.
At first, I thought there should be a chain of values update. For example, after calculating new index, we know value on index 0 is going to replace on index 3. Then I just need to know where to put value that used to be on index 3, and ah-ha, it’s index 6. The calculation loops for array_size times, so that all values have been replaced once. For array sized 7 and shifting by 3, I can come up with a chain like 0 -> 3 -> 6 -> 2 -> 5 -> 1 -> 4. It can work!
However, I found example 2 couldn’t be solved using this solution. Basically, there’s a internal loop between 0 -> 2 -> 0. Index 1 and 3 can never been touched. Then I started to think, since array size can be divided by shift distance, that could cause mini internal loops occur. What if we check the mod in advance, so that we know how many mini loops? In this case, we know there can be n mini loops, and each loop sized k. Once we finish the mini loop, we start the next loop at index i+ 1.
It can pass the second test case now. But soon I found, for given test set at size 6 and shift distance at 4, there’s also internal loops but mod doesn’t tell. It’s because right shifting by 4 is equivalent to left shifting by 2, whereas 6 can be divided by 2. So I add conditions beforeahead to tell handle the case.
Now everything works! Ready to submit the code! Unfortunatly, the code passed 36/37, only failed on one large test case, where there are 1⁰⁵ items in array and k = 54944.
It’s hard to imagine why only this large dataset failed. I check the data size, it’s within interger boundary, so should be no overflow/underflow happens. I have to use my IDE for debugging. I suspect it’s the index calculation error somewhere, so I print out all index replacement trace, then surprisingly find only 3125 indexes touched, although it’s looping for 1⁰⁵ times! I have to re-consider my assumption, that is internal loops only occurs if array_size % shift_distance == 0
Let’s say array size = C, shift distance = k,
index within the same loop are x + mk, where x is our starting index.
Having internal loop means x + mk = x + aC , means if you start at index x, after m moves, you come back to the same index x, after mod by C. To have the equation holds, it only requires mk = aC , where m and a both integers, and m < C.
This kinda explains why the code works for small data, but failed on large ones, because with larger C, it’s easier to find a value m and a that make the equation true. But for smaller C = 7, k = 3 case, the smallest m=7 where we have already looped all values.
It also means, internal loop doesn’t exist only if C and k has 1 as the greatest common factor… So the actual loop size m, is the C divided by GCF(C, k)…
I don’t want to write a code for GCF here, so will just take the easiest solution.. which is three times array reverse..
Even though my initial way doesn’t really work, it’s a good thinking practice!
My code
static public void rotate(int[] nums, int k) {
k = k % nums.length;
if (k == 0) return;
int round = 1;
if (nums.length % k == 0 || nums.length % (nums.length - k) == 0) {
round = k;
}
for (int i = 0; i < round; i ++) {
int ind = i, total = nums.length / round;
int val = nums[ind];
while (total -- > 0) {
int ind2 = ((ind + k) % nums.length);
int val2 = nums[ind2];
nums[ind2] = val;
val = val2;
ind = ind2;
}
}
}