Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?

### Using intermediate array

- First find out correct number of rotations using mod
- Create temporary array
- Push array elements into that temporary array
- Copy that temporary array into original array

function rotateArray(nums,k) { if(isNaN(k) || k < 0) { throw "provide valid order"; } if(nums.length == 0) { throw "provide valid array"; } if(k > nums.length) k=k%nums.length; var result = []; for(var i=0; i < k; i++){ result[i] = nums[nums.length-k+i]; } var j=0; for(var i=k; i<nums.length; i++){ result[i] = nums[j]; j++; } nums = result.slice(); console.log(nums); }

#### Complexity

Observe above demo. It will take O(n) space and O(n) time

### Using bubble rotate

By using bubble swap, we can solve this problem. Move array elements from right side to left side of the array using bubble swap

function rotateArray2(arr, order) { if(isNaN(order) || order < 0) { throw "provide valid order"; } if(arr.length == 0) { throw "provide valid array"; } for (var i = 0; i < order; i++) { for (var j = arr.length - 1; j > 0; j--) { var temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } console.log(arr); }

#### Complexity

Observe above demo. It will take O(1) space and O(n*k) time

### Using Reversal

Divide array into 2 parts based on given order. Reverse first part and then reverse second, then reverse whole array

function rotate3(arr, order) { if(isNaN(order) || order < 0) { throw "provide valid order"; } if(nums.length == 0) { throw "provide valid array"; } order = order % arr.length; //length of first part var a = arr.length - order; reverse(arr, 0, a-1); reverse(arr, a, arr.length-1); reverse(arr, 0, arr.length-1); console.log(arr); } function reverse(arr, left, right){ while(left < right){ var temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } rotate3([1,2,3,4,5,6],3);

#### Complexity

Observe above demo. It will take O(1) space and O(n) time

This comment has been removed by the author.

ReplyDeleteSkeleton Onese

ReplyDeleteRed Angry Birds Onese

Shaun the Sheep Onese