0
$\begingroup$

I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody give me the intuition or simple math explanation for me to understand.

void rotate(vector<int>& nums, int k) {
    k %=nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin()+k);
    reverse(nums.begin()+k, nums.end());
}
Improve this question
$\endgroup$
1
$\begingroup$

Imagine flipping a deck of cards over, then dividing it into two parts and flipping each part over. The cards in each part end up in their original order because they're flipped twice. The first flip also swaps the two parts. The net effect is the same as cutting the deck, i.e. rotating it.

Improve this answer
$\endgroup$
6
  • $\begingroup$ sry Can;t understand the word flip?. $\endgroup$ – Allan Sep 28 '20 at 7:17
  • $\begingroup$ You say [1,2,3,4,5,6,7,8,9,10] flipped = [10,9,8,7,6,5,4,3,2,1] $\endgroup$ – Allan Sep 28 '20 at 7:18
  • $\begingroup$ divide into two parts [10,9,8,7,6] and [5,4,3,2,1] and $\endgroup$ – Allan Sep 28 '20 at 7:18
  • $\begingroup$ flip = [6,7,8,9,10] and [1,2,3,4,5] $\endgroup$ – Allan Sep 28 '20 at 7:18
  • $\begingroup$ How they end up in their original position for ex, 1 ends up in 6th position $\endgroup$ – Allan Sep 28 '20 at 7:19
0
$\begingroup$

For me it is helpful to see the proof. Consider the equivalent algorithm where you reverse $0...n-k-1$, reverse $n-k...n-1$, and finally reverse $0...n-1$.

Let’s say you are rotating an array of $n$ elements by $k$. For $0 \leq i \leq n-k-1$, the new position of element $i$ is $i+k$. For $ n-k \leq i \leq n-1$, the new position of element $i$ is $i+k-n$.

Now let’s look at the transformation when following the algorithm above. For an element at position $i$, the first reverse will put that element at $n-i-1$. The third reverse will take an element at position $j\leq n-k-1$ and put it at $n-k-j-1$. Therefore, an element beginning at position $i \geq n-k-1$ will end up at $n-k-(n-i-1)-1=k+i$. A similar proof follows for the elements in the upper part of the array rotation ($i\geq n-k$).

The proof for the algorithm you posted above is essentially the same, the difference being that the elements in the sub array rotations are no longer necessarily all $\leq n-k-1$ or $\geq n-k$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.