1

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?

Improve this question
2
  • 1
    I think this belongs at codereview.stackexchange.com Commented Mar 8, 2020 at 21:17
  • 2
    @mplungjan I disagree. Performance is always important in code, the only question is to what degree. How fast something is in big O notation, which this question clearly mentions, is a purely objective measure. Commented Mar 8, 2020 at 22:25

4 Answers 4

Reset to default
2

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));

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Interesting, but seems to be buggy (unless I'm missing something): rotate([1,2,3,4,5,6,7], 1) -> [3, 4, 5, 6, 7, 1, 2] rotate([1,2,3,4,5,6,7], 0) -> [2, 3, 4, 5, 6, 7, 1]
Oh, I was rotating to the left, have to pass a negative index instead
Another findings I'd like to highlight: 1) this does not edit original array, but returns new one; 2) does not work for k > 7
@CertainPerformance I think you need something like k = k % nums.length; somewhere in your code
1

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).

Improve this answer

1 Comment

This is constant time, or O(1)
0

unshift combined with pop seems to do a trick:

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

Comments

0 
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--;
 }
}
Improve this answer

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.