CODEWITHSUNDEEP
javascriptarraysalgorithmdata-structures
SamuraiJack
SamuraiJack

Reputation: 5549

Better/faster algorithm to rotate an array?

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

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3

Output: [5,6,7,1,2,3,4]

Explanation:

Step 1: [7,1,2,3,4,5,6]

Step 2: [6,7,1,2,3,4,5]

Step 3: [5,6,7,1,2,3,4]

My Solution:

var rotate = function(nums, k) {
while(k>0){ 
 let lastelm = nums[nums.length-1];
  for(let i =nums.length; i>0;i--){
    temp = nums[i-1];
    nums[i-1] = nums[i-2];    
  }
  nums[0]=lastelm
  k--;
 }     
};

I think my solution is O(k*nums.length)

I am modifying the entire array as many times as k

What could be a better approach to this?

Upvotes: 1

Views: 708

Answers (4)

Влад Скригун
Влад Скригун

Reputation: 1

var rotate = function(nums, k) {
  k = k % nums.length;
  revNums(nums, 0, nums.length - 1);
  revNums(nums, 0, k -1);
  revNums(nums, k , nums.length - 1);
};

var revNums = function(arr, start, end){
while(start < end){
    [arr[start], arr[end]] = [arr[end], arr[start]];
    start++;
    end--;
 }
}

Upvotes: 0

CertainPerformance
CertainPerformance

Reputation: 371049

You can use .slice to take two slices out of an array - one starting from the beginning, ending in the middle, and the other slice starting in the middle and ending at the end. Then just re-combine them in reverse order:

const rotate = (nums, k) => [...nums.slice(-k), ...nums.slice(0, -k)];
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 3));

If you have to mutate the existing array, then:

const rotate = (nums, k) => {
  const moveAfter = new Array(k).concat(nums.slice(0, -k));
  Object.assign(nums, nums.slice(-k), moveAfter);
  return nums;
};
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 3));

If k may be larger than the length of the array, use modulo on it first:

const rotate = (nums, kPossiblyOutOfRange) => {
  const k = kPossiblyOutOfRange % nums.length;
  return [...nums.slice(-k), ...nums.slice(0, -k)];
}
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 8));
console.log(rotate([1,2,3,4,5,6,7], 3));

Upvotes: 2

Makhno
Makhno

Reputation: 441

unshift combined with pop seems to do a trick:

var rotate = function(nums, k) {
    while (k > 0) { 
        nums.unshift(nums.pop());
        k--;
    }
}

Upvotes: 0

Dave
Dave

Reputation: 9085

The easiest way to do this is just to keep track of the shift when you read or write to the array. I.e. store a constant 'shift' and when you read or write from the array at index i, make the adjustment to (i + shift) % (array size).

Upvotes: 1

Related Questions