DEV Community

Cover image for Leetcode 189: Rotate Array JavaScript Solution.
Tochi
Tochi Subscriber

Posted on

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;
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
  }

};
Enter fullscreen mode Exit fullscreen mode

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]
}  
};
Enter fullscreen mode Exit fullscreen mode

Complexity

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

Top comments (0)