Day 4. two pointers - move zero(es) to the end of array

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

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.

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

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

// 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

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

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
• 2460. Apply Operations to an Array