#189 Rotate Array

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 <= 105

Solution 1: Brute force

/*
the error generates while submit it to leetcode server
Error : Time Limit Exceeded
*/
void rotateBruteForce(vector<int>& nums, int k)
{
	for(int j=0; j<k; j++)
	{
		for(int i=1; i < nums.size(); i++)
		{
			swap(nums.at(0), nums.at(i));
		}
	}
}

Solution 2 : Use extra space with size n (optimized)

/*
Use extra space with size n
*/
void rotate(vector<int>& nums, int k) {
        vector<int> t(nums.size(),0);
        for(int i=0; i<nums.size(); i++)
            t[(k+i)%nums.size()] = nums[i];
        nums=t;
    }

Complete Code:

// Cyclically rotate an array by one
#include <bits/stdc++.h>
using namespace std;

/*
the error generates while submit it to leetcode server
Error : Time Limit Exceeded
*/
void rotateBruteForce(vector<int>& nums, int k)
{
	for(int j=0; j<k; j++)
	{
		for(int i=1; i < nums.size(); i++)
		{
			swap(nums.at(0), nums.at(i));
		}
	}
	for(int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	cout << endl;
}

/*
Use extra space with size n
*/
void optimizedRotation(vector<int>& nums, int k)
{
	// create extra space(temp vector) with size nums.size()
	vector<int> t(nums.size(),0);
	// fill the temp vector
	for(int i=0; i<nums.size(); i++)
		t[(k+i)%nums.size()] = nums[i];

	//replace nums with temp vector
	nums=t;
	// Print the vector
	for(int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	cout << endl;
}

int main()
{
	vector<int> v = {1,2,3,4,5,6,7,8};
	optimizedRotation(v,3);

	return 0;
}