Move Zeros

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Move all zeros in place to the end of the array
• Maintain the relative order
• Do not use additional array
• Must solve in $O(n)$ space

What is Being Asked?

(One sentence on the actual task.)

• Move all zeros in place to the end of the array

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Moving zero to the end is equal to moving non-zero to left
• Moving non-zero to left is more intuitive
• Left pointer denotes where to put element
• Right pointer is the value to swap

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Start at the left most element
• Left and Right pointers are same
• Iterate through each element (iteration is Right pointer)
• If non-zero value is found, swap with left and move left one place forward

Why This Works

(Explain the core reason the solution is correct.)

• Two Pointers
• We swap values in place until all zeros are at the end

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Two Pointers

Time & Space Complexity

• Time: O($n$) → Reason: Iterating through the array once
• Space: O($1$) → Reason: Not using any extra space except two variables

Code

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Input:  [4, 2, 4, 0, 0, 3, 0, 5, 1, 0]
        # Output: [4, 2, 4, 3, 5, 1, 0, 0, 0, 0]
        # left always moves one
        # right moves until condition

        # l, r = 0, 0
        # while l <= r and l < len(nums) and r < len(nums):
        #     while r < len(nums) and nums[r] == 0:
        #         r += 1
            
        #     if r < len(nums):
        #         nums[l], nums[r] = nums[r], nums[l]
        #         l += 1
        #         r += 1

        ## optimized solution
        left = 0
        for right, rightValue in enumerate(nums):
            if rightValue:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1

Common Mistakes / Things I Got Stuck On

• Over complicated while loop
• Better to figure out which Two Pointers technique is needed