I have a working solution for this problem that was accepted in LeetCode:

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

function rotate(nums, k) {

  for (let i = 1; i <= k; i += 1) {

    const poppedNum = nums.pop();

    nums.unshift(poppedNum);

  }



  return nums;

}



// rotate([1, 2, 3, 4, 5, 6, 7], 3) -> [5, 6, 7, 1, 2, 3, 4]

Questions:

• Would the time complexity be $O(k)$ and space complexity be $O(1)$?




• Is there a better way to solve this? The question asked to rotate the elements in-place if possible, but I am not sure how to accomplish this at the moment.

Review

Not bad, but there is room for a few improvements to avoid some possible problematic input arguments.

Style

Some points on your code.

• The names nums and k could be better, maybe array and rotateBy
  


• Try to avoid one use variables unless it makes the lines using them to long. Thus you can pop and unshift in one line nums.unshift(nums.pop());
  


• Idiomatic javascript uses zero based loop counters rather than starting at 1. Thus the loop would be for (let i = 0; i < k; i++) {
  

Complexity

Your complexity is $O(n)$ and storage $O(1)$ where $n$ is the number of rotations, the range $n>0$

However consider the next examples

rotate([1,2,3,4,5,6,7,8,9], 18); // Will rotate 18 times same as rotate 0

rotate([1,2,3,4,5,6,7,8,9], 8); // Will rotate 8 times same as rotate left 1

rotate([1], 8e9); // Will spend a lot of time not changing anything

Your function will do too much work if the rotations are outside the expected ranges, the rotation can be done in reverse in less steps, or rotating has no effect.

You can limit the complexity to $O(k)$ where $0<k<=n/2$

Rewrite

This is a slight improvement on your function to ensure you don't rotate more than needed.

function rotate(array, rotateBy) {

    rotateBy %= array.length;

    if (rotateBy < array.length - rotateBy) {

        while (rotateBy--) { array.unshift(array.pop()) }

    } else {

        rotateBy = array.length - rotateBy;

        while (rotateBy--) { array.push(array.shift()) }

    }

    return array;

}

Update

As vnp's answer points out the complexity of Array.unshift and Array.shift is not as simple as $O(1)$ and will depend on the array type. We can assume the best case for this problem, sparse array (effectively a hash table) and thus will grow/shrink down at $O(1)$

In that case the function above has a mean complexity of $O(log(n))$ of all possible values of $k$

Note that if the cost of grow/shrink operations is $O(n)$ (dense array) this will add $n$ operations for each $k$ making the above $O(kn)$ with $0<=k<(n/2)$ Expressed in terms of $n$ or $k$ only it remains $O(log(n))$ or $O(k)$

You could also use Array.splice

 array.unshift(...array.splice(-rotateBy,rotateBy));

However under the hood the complexity would be a little greater $O(2n)$ (which is still $O(n)$) as splice steps over each item to remove and add to a new array. Then ... steps over them again to unshift each item to the array.

The storage would also increase as the spliced array is held in memory until the code has finished unshifting them making storage $O(n)$

If the array contained all the same values the rotation would have no effect thus all rotation could be done in O(1). However there is no way to know this without checking each item in turn.

The time complexity really depends on the unshift time complexity. ECMA does not specify it, but I would expect that it is not constant. I would not be surprised if it is actually linear in the size of the array. If so, the complexity of rotate would be $O(nk)$.

In fact, I tested the performance of your code by timing your rotate by 1, for arrays of size from 100000 to 100000000, doubling the size every time. The results (in milliseconds) are

1, 3, 8, 14, 29, 33, 69, 229, 447, 926

I did few runs, the exact numbers were different, but consistent. You can see that as size doubles the run time (at least) doubles as well.

And again, it was rotation by 1. Rotation by k will take proportionally longer.

There are few classic algorithms which perform the rotation in true $O(n)$ complexity, that is their execution time does not depend on k. One is extremely simple to code, but takes effort to comprehend. In pseudocode:

    reverse(0, k)

    reverse(k, n)

    reverse(0, n)

Notice that each element is moved twice. This is suboptimal. Another algorithm moves each element exactly once - right into the place where it belongs. I don't want to spoil the fun of discovering it. Try to figure it out (hint: it needs to compute gcd(n, k)).

That said, the leetcode problem only asks to print the rotated array. I would seriously consider to not actually perform rotation, but

    print values from n-k to n

    print values from 0 to n-k

It feels like cheating, but in fact it is valid, and sometimes very useful technique.

Think twice before modifying function parameters

The posted code modifies the content of the input array nums and also returns it.
When a function returns something,
it can be confusing if it also modifies the input — a side effect.
Modifying the input and not returning anything (void in other programming languages) is not confusing.
I think it's important to make a conscious of choice between two non-confusing behaviors: either modify the input and return nothing, or not modify the input and return the result as a new object.

Insert k items at the start of an array in one step instead of one item in k steps

In most programming languages, and I think in the context of this exercise, "array" usually means a contiguous area of memory. Inserting an element at the start is implemented by copying existing elements to shift them in memory by 1 position.

For this reason, for a solution to the array rotation problem, I would avoid repeatedly inserting elements at the start of the array, to avoid repeated copying of elements. Even if arrays in JavaScript may behave differently, I would prefer a solution that doesn't raise questions about the potential underlying implementation of arrays, and looks objectively easier to accept.

That is, I would prefer to store k values in temporary storage, shift the other elements by k steps (iterating over them only once), and then copy back the k elements to the correct positions.

function rotate(nums, k) {

  k %= nums.length;

  const rotated = new Array(nums.length);

  for (let i = 0; i < k; i++) {

    rotated[i] = nums[nums.length - k + i];

  }

  for (let i = 0; i < nums.length - k; i++) {

    rotated[i + k] = nums[i];

  }

  return rotated;

}

This is $O(n)$ in both time and space.
The extra space is needed to avoid modifying the input.
If we preferred modifying the input,
then only $O(k)$ extra space would be needed,
for temporary storage of elements that would be overwritten.

Taking advantage of JavaScript's features

Slightly more expensive in terms of time and space,
but my preferred solution would make better use of the built-in functions on arrays in JavaScript,
in much more compact code:

function rotate(nums, k) {

  k %= nums.length;

  const m = nums.length - k;

  return nums.slice(m).concat(nums.slice(0, m));

}