Given an array, rotate the array to the right by k steps, where k is non-negative.

Example :

Input: nums = [-1,-2,4,5], k = 2
Output: [4,5,-1,-2]
Explanation:
rotate 1 steps to the right: [5,-1,-2,4]
rotate 2 steps to the right: [4,5,-1,-2]

Approach 1: Brute Force

Naive solution comes in mind is that pop item from array and add to front.

var rotate = function(nums, k) {
k = k % nums.length;
let i = -1;
while(++i < k) {
nums.unshift(nums.pop());
}
return nums;
};

Time Complexity : O(k*n) Space Complexity : O(0)

while loop runs k times and inside unshift function runs once. unshift() function take O(n) times so Time complexity O(k*n).

Approach 2: Linear With Extra Space

We can optimise time complexity with the help of extra array. In that array we can keep item with k spaces.

let say, we have an array nums = [2,1,4] , k = 2; tempArray = [] ;

so first item of nums move to (i+k) = 0 + 2 = 2th index of tempArray

what about second item of nums, (i+k) = 1 + 2 = 3th index of tempArray which is not gonna happened right. Here comes modulo operator to help.

(i+k) % arraylength = (1 + 2) % 3 = 3 % 3 = 0th index of tempAarray.

After creating new array just we have to put new array item to existing array.

var rotate = function(nums, k) {
let len = nums.length,
tempArr = [],
i = -1;
k = k % len;
while(++i < len) {
tempArr[(i+k) % len] = nums[i];
}
for(i = 0; i < len; i++)
nums[i] = tempArr[i];
return nums;
};
Time Complexity : O(n) Space Complexity : O(n)(cause we create new array)

Approach 3: Linear Without Extra Space

But we can produce linear solution without creating extra space.We are going to reverse parts of the array three times.

First time just reverse entire array, then reverse the first k element of the array, lastly reverse from k to end of the array.

So we need 3 reverse , first reverse function takes n times & rest 2 reverse takes total n times.

Time complexity n + n = 2n, 2 is constant here, So O(n),

var reverse = (nums, start, end) => {
while(start < end) {
let temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++, end--;
}
}
// O(n) Space O(1)
var rotate = function(nums, k) {

let len = nums.length;
k = k % len;

reverse(nums, 0, len - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, len - 1);

return nums;
};