Move Zeros - Two Pointers / Same Direction

Problems
1

https://algo.monster/problems/move_zeros

2

The answer is far too close to the question. It’d be better if the answer could be collapsed (similar to navbars in a hamburger or the summary tag in html).

3

Agreed!

4

true

5

Why don’t we have a list of problems for a pattern so I can jump to the end of the pattern instead of starting at the beginning everytime?
For e.g: we can have a list like this

  • Two pointers
    • Same direction
      • Remove duplicate
      • Middle of a Linked List
    • Opposite direction
    • Window sliding
6

Alternative with queue:

from typing import List
from collections import deque

def move_zeros(nums: List[int]) -> None:
    left = 0
    while nums[left]:
        left += 1
    
    zeros = deque([])
    for right in range(left + 1, len(nums)):
        if nums[right] == 0:
            zeros.append(right)
            continue

        nums[left], nums[right] = nums[right], nums[left]
        zeros.append(right)
        left = zeros.popleft()
7

Probably goes against spirit, but this is stable_partition(nums.begin(), nums.end(), [] (int num) { return num > 0; }); in C++

8

LC: https://leetcode.com/problems/move-zeroes/

9

Python one pass:
def move_zeros(nums: List[int]) → None:
nonZerosSeen = 0
for index in range(len(nums)):
num = nums[index]
if num != 0:
nums[nonZerosSeen] = num
if nonZerosSeen != index:
nums[index] = 0
nonZerosSeen += 1

10

Alternative approach makes much more sense, but it has nothing to do with Two Pointers.

11

I agree! Much more intuitive and I probably would have thought about that approach if the section was not labelled “Two Pointers”

12

The “alternative” is just meant to show how you could come up with the actual solution if it didn’t occur to you right away. aka you might have better luck coming up with the two pointer solution from patterns observed in the alternative approach. You’re not actually meant to submit the alternative approach as your final answer. It’s a technique - find a naive solution, then try and find a better solution based on patterns seen in the naive one.

13

I think the answer is neater than mine

def move_zeros(nums: List[int]) -> None:
    left = 0
    right = 0
    while right < len(nums):
        while left < len(nums) and nums[left] != 0:
            left += 1
        right = left + 1
        while right < len(nums) and nums[right] == 0:
            right += 1
        if right < len(nums):
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right += 1