Day 16: Move Zeroes: Two Pointers - leetcode - Python3

 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]

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

SOLUTION

class Solution:

    def moveZeroes(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in-place instead.

        """

        left: int = 0

        for right in range(len(nums)):

            if nums[right]:

                nums[left], nums[right] = nums[right], nums[left]

                left += 1

           

        return nums

Time Complexity: O(n)

Space Complexity:O(1) which means it uses constant space regardless of the size of the input list

How it works:

1. It initializes two variables, left and right, to keep track of the positions in the list. The left variable represents the index where the next non-zero element should be placed, and the right variable iterates over the list elements.

2. It starts iterating over the nums list using a for loop that ranges from 0 to the length of the list.

3. Inside the loop, it checks if the current element at index right is non-zero (since 0 evaluates to False in Python). If the element is non-zero, it proceeds with the next steps.

4. It swaps the element at index left with the element at index right using a simultaneous assignment. This effectively moves the non-zero element to the correct position at the beginning of the list. After the swap, the left index is incremented by 1.

5. The loop continues until all elements in the nums list have been processed.

6. Finally, it returns the modified nums list. Since the modification is done in-place, the original list is modified directly.

Overall, this code effectively moves all the non-zero elements to the beginning of the list while maintaining their relative order.