2. Rotate Array

Different solutions to array rotation.

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]

Solution I

class Solution
{
public:
    void rotate(vector<int> &nums, int k)
    {

        int len = nums.size();
        int rotate = 0;
        int temp, j, i, r;

        rotate = k % len;

        if (rotate != 0)
        {
            r = len - rotate; //finding no of left rotation
            int g = gcd(rotate, r);
    
            for (i = 0; i < g; i++)
            {
                j = i;
                temp = nums[j];
                while (1)
                {
                    int move = j + r;
                    if (move >= len)
                        move = move - len;

                    if (move == i)
                        break;

                    nums[j] = nums[move];
                    j = move;
                }
                nums[j] = temp;
            }
        }
    }
};

Solution:- Create a new array with rotated elements by finding the number of elements to be rotated.

This solution uses O(n) Time complexity and O(n) Space Complexity.

This solution can be optimized more by using O(n) time complexity and O(1) space complexity. Can be done by using in-place operations.

Solution II

vector<int> solve(vector<int> &nums, int k)
{
    int n = nums.size();

    reverse(nums.begin(), nums.end());

    int rotate = k % n;

    int i = 0;
    int j = n - rotate - 1;

    while (i < j)
    {
        swap(nums[i], nums[j]);
        i++;
        j--;
    }

    i = n- rotate;
    j = n - 1;

    while (i < j)
    {
        swap(nums[i], nums[j]);
        i++;
        j--;
    }

    return nums;
}

This solution uses O(n) Time complexity and O(1) Space Complexity. This solution is based on Juggling Algorithm.