Tags: javascript, algorithms, arrays, circular replacement

Imagine a merry-go-round, where each horse is a number from an array. Now, let’s say we want to rotate this merry-go-round by a certain number of steps, k, to the right. This is essentially what we’re doing when we’re asked to rotate an array.

Let’s take an example:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Rotate 1 step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]

If k is equal to the length of the array, the array doesn’t change. To simplify the operation, we can set k = k % nums. For any element i in the array, we can calculate its new position after the rotation as (i + k)%nums. However, we can’t directly move the elements, because the original element at position (i + k)%nums would be lost. To solve this problem, we first need to make a copy of the array.

Here’s the code implementation:

var rotate = function (nums, k) {
    k = k % nums.length;
    const copy=[...nums];
    for (let i = 0; i < nums.length; i++) {
        const target_index =(nums.length+i-k)%nums.length;
        nums[i] = copy[target_index]
    }
    return nums;
};

The time complexity of this code is O(n), and the space complexity is also O(n), because we make a copy of the array, which consumes extra memory.

But what if we only copy the element that is being replaced? We can do this by following these steps:

_1. Copy the element at position a to tmp.

_2. Copy the element at position b to position a.

_3. Copy the element at position c to position b.

…

_n. Copy the element at position a to position n (Note that the element at position a is actually in tmp, so we are copying tmp to position n).

Here’s the code implementation:

var rotate = function (nums, k) {
    k = k % nums.length;
    let count=0;
    let start = 0;
    let target=start;
    let target_value = nums[start];
    for(;;count++){
        if(count===nums.length)break;
        let source = (target+nums.length -k)%nums.length;
        nums[target]=source==start?target_value:nums[source];
        target=source;
        if(target===start){
            start++;
            target_value = nums[start];
            target=start;
        };
    }
    return nums;
};

The time complexity of this code is still O(n), but the space complexity is now O(1).

Finally, since we’re using JavaScript, we can also use JavaScript’s built-in array function splice to achieve the same result:

  1. Use the modulus operator % to ensure that k does not exceed the length of the array, to avoid unnecessary operations.
  2. Use the splice method to cut k elements from the end of the array and make them a new subarray.
  3. Use the splice method to insert this subarray at the beginning of the array, to achieve the rotation to the right by k positions.

Here’s the code implementation:

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

And there you have it - the merry-go-round of numbers, spinning to the right, all thanks to the magic of JavaScript!