Day 4. two pointers - move zero(es) to the end of array
Published: 2023-04-10 07:12:19

Now I'm more used to remind myself of **two pointers**, I tried not to look at solutions or other people's posts. And I made it without looking them up!

### [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)

Description: Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. **Note that you must do this in-place without making a copy of the array.**

```js
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]
```

### Learning points
- I initially just tried the easy JS way, using unshift and push methods. But it led to *out of memory*.
- do I want to count the total number of zero and use it somehow? how to replace the original zero spot with non-zero? how to swap non-zero and zero? 
- I kind of thought of #2 approach in the editorial post, `counting the number of zeroes and fill at the end of array`. But I didn't think too deep and thought it may not be two pointers. But the explanation made sense. 

**[Editorial post explanation. good](https://leetcode.com/problems/move-zeroes/editorial/?envType=study-plan&id=algorithm-i)**

```
This is a 2 pointer approach. 
The fast pointer which is denoted by variable "cur" 
does the job of processing new elements. If the newly 
found element is not a 0, we record it just after the
 last found non-0 element. The position of last found 
non-0 element is denoted by the slow pointer 
"lastNonZeroFoundAt" variable. 
```

### Attempts

**1. Initial JS unshift, push methods**
```js
// solution 1: unshift, push, O(n) for loop
// Runtime error: JS heap out of memory
for(let i = 0; i < nums.length; i++) {
    if(nums[i] == 0) {
        nums.unshift();
        nums.push(0);
    }
}
```

**2. Next pseudo-code idea process with two pointers**
- move all the zeroes to the front. 
- reverse the entire array. `[0, 0, 0..]` would go to the end of array.
- reverse `non-zero partial array` only. `[12, 10, 3, 1] to [1, 3, 10, 12]`
- (I was maybe caught up with reverse/rotate idea because I just finished that quiz right before this lol)
- I realized that `[1, 2, 3, 0, 0, 4, 5]` this test case still wouldn't work with the current idea. 

**3. Better idea process with two pointers**
- Putting the zeroes to the front, and then reverse blah blah, which already seems complicated than it should be.
- I thought there should be a way to simplify this.
- I tried to use **two pointers to swap non-zero and zero to move the zeroes to the latter index**, not to the front. 

### Codes

**Final Pseudo code**
1. lower, upper pointers: start from index 0, 1
2. compare nums[lower] and nums[upper]
3. if nums[lower] is 0, nums[upper] is non-zero, we swap and put non-zero to the front. Then, we increase both pointers by 1: lower++, upper++
4. if nums[lower] and nums[upper] are both 0, we don't swap. We only increase upper+1 to find next non-zero. 
5. if nums[lower] and nums[upper] are both non-zero, we need to find next zero & non-zero combinations. So we increase both pointers by 1: lower++, upper++

- At first, I missed the #5 point, so it returned time limit exceeded error.

**Final code**
```js
let lower = 0;
let upper = lower + 1;
while(upper < nums.length) {
    if(nums[lower] == 0 && nums[upper] == 0) {
        // increment p2 only to find non-zero element
        upper++;
    } else {
        if(nums[lower] == 0 && nums[upper] != 0) {
            // swap non-zero and zero 
            let non_zero = nums[upper];
            nums[upper] = 0;
            nums[lower] = non_zero;
        } 
        // increment both pointers
        // when one or both are non-zero
        lower++;
        upper++;
    } 
}
```

**Solution 2 of editorial post**
```c++
void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    // If the current element is not 0, then we need to
    // append it just in front of last non 0 element we found. 
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
 	// After we have finished processing new elements,
 	// all the non-zero elements are already at beginning of array.
 	// We just need to fill remaining array with 0's.
    for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
        nums[i] = 0;
    }
}
```

### Relevant problems or quizzes
- [27. Remove Element](https://leetcode.com/problems/remove-element/description/)
- [2460. Apply Operations to an Array](https://leetcode.com/problems/apply-operations-to-an-array/description/)

![related algorithm problems](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i7g3u4xnko7zc5w2me9a.png)