Move Zeroes - Python Solution

1. Introduction

The "Move Zeroes" problem is a common array manipulation challenge that involves moving all zeros in an array to the end while maintaining the order of non-zero elements. This problem tests the ability to modify arrays in-place efficiently, a key skill in optimizing space complexity in algorithms.

Problem

Given an integer array nums, the task is to move all zeros to the end of the array while keeping the relative order of the non-zero elements unchanged. The operation must be performed in-place without using additional arrays or copying the original array.

2. Solution Steps

1. Initialize a pointer lastNonZeroFoundAt to keep track of the position of the last non-zero element found.

2. Iterate through the array.

3. For each non-zero element, swap it with the element at lastNonZeroFoundAt and increment lastNonZeroFoundAt.

4. Continue this process until the end of the array is reached.

5. As a result, all zeros are moved to the end, and the relative order of non-zero elements is maintained.

3. Code Program

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[lastNonZeroFoundAt], nums[i] = nums[i], nums[lastNonZeroFoundAt]
            lastNonZeroFoundAt += 1

# Example Usage
nums = [0,1,0,3,12]
moveZeroes(nums)
print(nums)  # Output: [1,3,12,0,0]

nums = [0]
moveZeroes(nums)
print(nums)  # Output: [0]

Output:

[1,3,12,0,0]
[0]

Explanation:

1. Pointer Initialization: lastNonZeroFoundAt is used to track the position for swapping non-zero elements.

2. Iterative Approach: The array is iterated to find non-zero elements.

3. Element Swapping: Each non-zero element is swapped with the element at lastNonZeroFoundAt.

4. Incrementing Pointer: lastNonZeroFoundAt is incremented each time a non-zero element is encountered, effectively pushing zeros to the end.

5. In-Place Modification: The array is modified in-place, ensuring O(1) space complexity.

6. Efficient Solution: The solution has O(n) time complexity, where n is the length of the array.

7. Practical Use Case: Demonstrates an efficient approach to array manipulation without extra space.