Leetcode 189: Rotate Array JavaScript Solution.

Intuition

My first idea was to split the array into two parts:

• The last k items in the array.
• All the items that come before those last k items.

But before doing that, I make sure to update k like this:

k = k % nums.length;

This step is important because sometimes k can be larger than the length of the array. If k is larger, rotating the array by k times is the same as rotating it by the remainder after dividing k by the array’s length.

Example:

Suppose nums.length = 7 and k = 10.

10 % 7 = 3.

This means rotating the array 10 times is really the same as rotating it 3 times, because after 7 full rotations, the array looks the same again. So you can think of it as: rotate 7 times (which resets the array), then rotate 3 more times.

After that:

• Create two smaller arrays (one for the last k items, one for the rest).
• Merge those two arrays together.
• Copy the merged result back into the original nums array.

Approach

First I set k to k % nums.length (I explained why above). Then I created a copy of the nums array and call it numsCopy.

After that, I looped through the nums array and for each index I added k to it. This is done to determine the new position of each item when nums is rotated k times.

Now there are two ways to go about the next step. Either we use modulus and say old index plus k (i + k) and then check if the sum is greater that nums.length-1. If it is we'll subtract nums.length from the sum.

Example:

Suppose i = 4, k = 3 and nums.length = 7.

let idx = i + k;

if(idx < nums.length - 1){
   idx = idx - nums.length;
}

Or we can use modulus and do old index plus k modulus nums.length ((i + k) % nums.length). That way we get the new index from the remainder.

let idx = (i + k) % nums.length;

Both solutions give the new index or position of each item in nums.

After the new index is gotten, we modify the nums array with the duplicate array by doing:

nums[idx] = numsCopy[i]

Solution

Initial Solution:

const rotate = (nums, k)=> {

  k %= nums.length;

  const kArray = [];

   for (let i = nums.length - k; i < nums.length; i++) {
     kArray.push(nums[i]);
   }

   const firstPartArray = [];

   for (let i = 0; i < nums.length - k; i++) {
     firstPartArray.push(nums[i]);
   }

  const rotatedArr =[...kArray, ...firstPartArray];

  for(let i = 0; i < rotatedArr.length; i++){
   nums[i] = rotatedArr[i]
  }

};

Improved Solution:

const rotate = (nums, k)=> {

k %= nums.length;

const numsCopy = [...nums];

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

  nums[rotateIdx] = numsCopy[i]
}  
};

Complexity

Both solutions have a time and space complexity of O(n) linear time.