Monday, March 30, 2015

LeetCode OJ - Rotate Array

Problem:

Please find the problem here.

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;
}


No comments :

Post a Comment