While the topic of this problem is clearly stated as two pointers, as I got obsessed with the question itself, I forgot the core idea or approaches. So I had to refer to some of the posts to realize how I can use two pointers to approach this problem.
189. Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps 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]
Learning points
- I get how
reverse all, reverse first part, reverse the other partapproach works the best. But still in the process of understanding how to come up with an idea from the first place hmm... - For all 3 types of solutions, a remainder operation for
kis the key to solve the cases in whichk > nums.length.
if(k > nums.length) {
k = k % nums.length;
}
Initial attempts
- Without
k%nums.lengthoperation, the solution 2 didn't work fornums=[1,2], k = 5test case. - solution 1 works fine, but when I submitted, it showed time limit exceeded - even with
k%nums.lengthoperation.
Solution 1
if(k > nums.length) {
k = k % nums.length;
}
for(let i = 0; i < k; i++) {
// pop from last index
let last = nums.pop();
// insert to first index
nums.unshift(last);
}
Solution 2
if(k > nums.length) {
k = k % nums.length;
}
let k_nums = nums.slice(nums.length - k, nums.length);
// slice: returns new array of start ~ end-1
// splice: delete original array from start ~ end-1
// O(n)
for(let i = k_nums.length - 1; i >= 0; i--) {
let n = k_nums[i];
nums.unshift(n);
}
- For solution 2, I first attempted to slide (make a new array of last k items -
[4, 5, 6]), splice (delete k items from the original -[0, 1, 2, 3]) and then concat. Then I tried to donums = a result of concat [4, 5, 6, 0, 1, 2, 3]. - But because the leetcode question was asking to modify the
nums- the original array, it didn't work. - So I had to find another way to modify the
nums. Here, I used unshift with for loop to add[4,5,6] in backwards orderto the beginning ofspliced array [0, 1, 2, 3].
Final code
var reverse = function(nums, lower, upper) {
while(lower < upper) {
let temp = nums[lower];
nums[lower] = nums[upper];
nums[upper] = temp;
lower++;
upper--;
}
}
var rotate = function(nums, k) {
// solution 3: FINAL
// reverse the entire array
reverse(nums, 0, nums.length - 1);
if(k > nums.length) {
k = k % nums.length;
}
// reverse first half array
reverse(nums, 0, k - 1);
// reverse last half array
reverse(nums, k, nums.length - 1);
};
Helpful posts
- https://leetcode.com/problems/rotate-array/solutions/3244055/rotation-array-clockwise-rotation-rotation-game-time-complexity-o-n-sc-o-1/?envType=study-plan&id=algorithm-i
- https://leetcode.com/problems/rotate-array/solutions/1730142/java-c-python-a-very-very-well-detailed-explanation/
- https://leetcode.com/problems/rotate-array/solutions/3360421/three-possible-java-solution-to-rotate-array/
Top comments (0)