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.
Top comments (0)