Solution to problem 283 “Move Zeroes” from LeetCode.

Problem Statement

Given an array nums of integers. You need to write a function that will move all zeros to the end of the array, while other numbers (non-zero) will remain in the same order.

Additional Conditions

• You need to solve the problem without using additional space – don’t create a new array
• Minimize the number of operations

Example

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Solutions

Using an Additional Array

Despite the additional condition - don’t create a new array - I suggest we still consider this solution.

Algorithm idea:

• Create a new empty array
• Create a counter - number of zeros in the original array
• Iterate through the original array
  • If the element is non-zero - add the element to the new array at the end
  • If the element is zero - increase the zero counter
• When we reach the end of the original array, add as many zeros to the end of the new array as in the counter

Complexity

Memory: O(n) Operations: O(n)

Pointer to the Last Non-Zero Element, Shifting Non-Zero Elements

Algorithm idea:

• Create a pointer to the last non-zero element (point to the initial element of the array)
• Iterate through the array, if the current element is non-zero:
  • Write it to the position of the last non-zero element
  • Move the pointer of the last non-zero element and move it to the next element
• After the pass, the pointer to the last non-zero element will point to the position from which you need to write zero elements, for this we iterate through the array from the position of the last non-zero to the end of the array and write zeros

func moveZeroes(nums []int)  {
    start := 0
    for idx := range nums{
        if nums[idx]!=0 {
            nums[start] =  nums[idx]
            start++
        }
    }
    for jdx := start; jdx< len(nums);jdx++ {
        nums[jdx] = 0
    }
}

Complexity

Memory: O(1) Operations: O(n)

Pointer to the Last Non-Zero Element, Swapping Zero and Non-Zero

Algorithm idea:

• Create a pointer to the last non-zero element (point to the initial element of the array)
• Iterate through the array, if the current element is non-zero:
  • Swap current with the last non-zero
  • Move the pointer of the last non-zero element and move it to the next element

func moveZeroes(nums []int)  {
    start := 0
    for idx := range nums{
        if nums[idx]!=0 {
            nums[start], nums[idx] = nums[idx], nums[start]
            start++
        }
    }
}

Complexity

Memory: O(1) Operations: O(n)

Interesting Observation

In this solution the number of operations is less than in the previous solution, but due to the slow operation of the swap operation – this solution will work a little longer