## Monday, March 30, 2015

### LeetCode OJ - Rotate Array

Problem:

Solution:

It would be trivial if I allocate an array and just do the copy and copy back. To challenge myself, I decided to make this in-place with O(1) extra memory.

If I wanted to shift by 2, then I need to save the element that I will overwrite to, and then move on to shift the other as follow

CI = 0
V  = 'A'
NI = 2

0 1 2 3 4 6
A B C D E F

Here my current index is 0, and I wanted to shift by 2, so I wanted to move A to the position of C, let's save C first, and overwrite position 2 with A.

CI = 2
V  = 'C'
NI = 4

0 1 2 3 4 6
A B A D E F

Now we move further, we have

CI = 4
V  = 'E'
NI = 0

0 1 2 3 4 6
A B A D C F

But then we are reaching back to where we were, so after the writing, we stops.

CI = 0
V  = 'A'
NI = 2

0 1 2 3 4 6
E B A D C F

The interesting thing about this particular case is that although we are reaching back to where we were, but we moved only 3 elements, in general, that happens when n % k == 0. In this case, we need to help the algorithm by moving the next cycle as well, so we move the current index to 1 and start the loop again, by accounting the number of move, we can easily make sure we moved all elements.

This one is fun problem to crack, I would have a hard time without running the code and debugging it. I guess I could write it on a whiteboard, but much harder to get it all right.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/rotate-array/

#include "LEET_ROTATE_ARRAY.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_ROTATE_ARRAY
{
class Solution {
public:
void rotate(int nums[], int n, int k) {
int moved_element = 0;
for (int start_index = 0; moved_element < n; start_index++)
{
int current_index = start_index;
int next_index;
int value_to_put = nums[start_index];
do
{
next_index = (current_index + k) % n;
int next_value = nums[next_index];
nums[next_index] = value_to_put;
value_to_put = next_value;
current_index = next_index;
moved_element++;
} while (next_index != start_index);
}
}
};
};

using namespace _LEET_ROTATE_ARRAY;

int LEET_ROTATE_ARRAY()
{
int A[] = { 1, 2, 3, 4, 5 };
Solution solution;
solution.rotate(A, 4, 2);
for (int i = 0; i < 5; i++)
{
cout << A[i] << " ";
}
cout << endl;
return 0;
}