Day 3. Two pointers - rotate array
Published: 2023-04-10 05:44:23

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](https://leetcode.com/problems/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 part` approach 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 `k` is the key to solve the cases in which `k > nums.length`.
```js
if(k > nums.length) {
  k = k % nums.length;
}
```

### Initial attempts

- Without `k%nums.length` operation, the solution 2 didn't work for `nums=[1,2], k = 5` test case.
- solution 1 works fine, but when I submitted, it showed time limit exceeded - even with `k%nums.length` operation. 

**Solution 1**
```js
    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**
```js
    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 do `nums = 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 order` to the beginning of `spliced array [0, 1, 2, 3]`. 

### Final code
```js
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/

![relevant or similar quizzes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qj0j5jivflpiixevulaw.png)

### Related problems / quizzes
- [61. Rotate List](https://leetcode.com/problems/rotate-list/description/)
- [Premium Only - 186. Reverse Words in a String II](https://leetcode.com/problems/reverse-words-in-a-string-ii/description/)
- [2607. Make K-Subarray Sums Equal](https://leetcode.com/problems/make-k-subarray-sums-equal/description/)