[Arrays] Move Zeroes

📋 This is my note-taking from what I learned in LeetCode!

Problem

Problem Link

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 <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

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

Hint #1:

In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

Hint #2:

A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

Solution

Solution Link

This question comes under a broad category of “Array Transformation”. This category is the meat of tech interviews. Mostly because arrays are such a simple and easy to use data structure. Traversal or representation doesn’t require any boilerplate code and most of your code will look like the Pseudocode itself.

The 2 requirements of the question are:

Move all the 0’s to the end of array.

All the non-zero elements must retain their original order.

It’s good to realize here that both the requirements are mutually exclusive, i.e., you can solve the individual sub-problems and then combine them for the final solution.

Approach 1: (Space Sub-Optimal) [Accepted]

Algorithm:

1. Find the number of zeroes in the input list ‘nums’ and store it in the variable ‘numZeroes’.
2. Create an empty list ‘ans’.
3. Iterate through each element in ‘nums’ and if the element is non-zero, append it to the list ‘ans’.
4. Append the number of zeroes in ‘nums’ at the end of the ‘ans’ list.
5. Iterate through each element in ‘nums’ and replace it with the corresponding element in ‘ans’. This will move all the zeroes in ‘nums’ to the end of the list while maintaining the order of the non-zero elements.

def moveZeroes(nums: list[int]) -> None:
    n = len(nums)

    # Count the zeroes
    numZeroes = 0
    for i in range(n):
        numZeroes += nums[i] == 0
        # nums[i] == 0 의 결과가 참이면 numZeroes 변수에 1을 더함

    # Make all the non-zero elements retain their original order.
    ans = []
    for i in range(n):
        if nums[i] != 0:
            ans.append(nums[i])

    # Move all zeroes to the end
    while numZeroes > 0:
        ans.append(0)
        numZeroes -= 1

    # Combine the result
    for i in range(n):
        nums[i] = ans[i]

nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums)

Complexity Analysis

• Space Complexity : O(n). Since we are creating the “ans” array to store results.
• Time Complexity: O(n). However, the total number of operations are sub-optimal. We can achieve the same result in less number of operations.

If asked in an interview, the above solution would be a good start. You can explain the interviewer(not code) the above and build your base for the next Optimal Solution.

Approach 2: (Space Optimal, Operation Sub-Optimal) [Accepted]

This is a 2 pointer approach. The fast pointer which is denoted by variable “cur” does the job of processing new elements. If the newly found element is not a 0, we record it just after the last found non-0 element. The position of last found non-0 element is denoted by the slow pointer “lastNonZeroFoundAt” variable. As we keep finding new non-0 elements, we just overwrite them at the “lastNonZeroFoundAt + 1” ‘th index. This overwrite will not result in any loss of data because we already processed what was there(if it were non-0,it already is now written at it’s corresponding index,or if it were 0 it will be handled later in time).

After the “cur” index reaches the end of array, we now know that all the non-0 elements have been moved to beginning of array in their original order. Now comes the time to fulfil other requirement, “Move all 0’s to the end”. We now simply need to fill all the indexes after the “lastNonZeroFoundAt” index with 0.

Algorithm:

1. Initialize a variable lastNonZeroFoundAt to 0.
2. Loop through the input array nums and check if the current element is non-zero.
3. If the current element is non-zero, append it to the position just in front of the last non-zero element found, which is indicated by the lastNonZeroFoundAt variable, and increment lastNonZeroFoundAt.
4. After all non-zero elements are processed, all the non-zero elements will be at the beginning of the array, up to the lastNonZeroFoundAt index. Fill the remaining indices with zeros.

def moveZeroes(nums: list[int]) -> None:
    lastNonZeroFoundAt = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[lastNonZeroFoundAt] = nums[i]
            lastNonZeroFoundAt += 1

    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = 0

nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums)

Complexity Analysis

• Space Complexity : O(1). Only constant space is used.
• Time Complexity: O(n). However, the total number of operations are still sub-optimal. The total operations (array writes) that code does is nnn (Total number of elements).

Approach 3: (Optimal) [Accepted]

The optimal approach is again a subtle extension of above solution. A simple realization is if the current element is non-0, its’ correct position can at best be it’s current position or a position earlier. If it’s the latter one, the current position will be eventually occupied by a non-0 ,or a 0, which lies at a index greater than ‘cur’ index. We fill the current position by 0 right away,so that unlike the previous solution, we don’t need to come back here in next iteration.

In other words, the code will maintain the following invariant:

1. All elements before the slow pointer (lastNonZeroFoundAt) are non-zeroes.
2. All elements between the current and slow pointer are zeroes.

Therefore, when we encounter a non-zero element, we need to swap elements pointed by current and slow pointer, then advance both pointers. If it’s zero element, we just advance current pointer.

With this invariant in-place, it’s easy to see that the algorithm will work.

Algorithm:

• Initialize a variable lastNonZeroFoundAt to 0.
• Iterate over the input list nums using a for loop with a variable cur.

• If the current element of nums is not 0:

  • Swap the current element with the element at index lastNonZeroFoundAt.

  • Increment lastNonZeroFoundAt by 1.

• The resulting list will have all the non-zero elements appear before the zeros.

def moveZeroes(nums: list[int]) -> None:
    lastNonZeroFoundAt = 0
    for cur in range(len(nums)):
        if nums[cur] != 0:
            nums[lastNonZeroFoundAt], nums[cur] = nums[cur], nums[lastNonZeroFoundAt]
            lastNonZeroFoundAt += 1

nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums)

Complexity Analysis

• Space Complexity : O(1). Only constant space is used.
• Time Complexity: O(n). However, the total number of operations are optimal. The total operations (array writes) that code does is Number of non-0 elements.This gives us a much better best-case (when most of the elements are 0) complexity than last solution. However, the worst-case (when all elements are non-0) complexity for both the algorithms is same.

For Better Understanding

Approach 3 Algorithm

nums = [0, 1, 0, 3, 12]

1. lastNonZeroFoundAt is initialized to 0.

2. The for loop begins with cur set to 0.

   nums[0] is 0, so we skip this iteration.

3. cur is incremented to 1.

   nums[1] is 1, so we swap nums[0] (which is 0) with nums[1]. Now nums is [1, 0, 0, 3, 12] and lastNonZeroFoundAt is 1.

4. cur is incremented to 2.

   nums[2] is 0, so we skip this iteration.

5. cur is incremented to 3.

   nums[3] is 3, so we swap nums[1] (which is 0) with nums[3]. Now nums is [1, 3, 0, 0, 12] and lastNonZeroFoundAt is 2.

6. cur is incremented to 4.

   nums[4] is 12, so we swap nums[2] (which is 0) with nums[4]. Now nums is [1, 3, 12, 0, 0] and lastNonZeroFoundAt is 3.

7. The for loop completes, and we’re done! The final value of nums is [1, 3, 12, 0, 0].

---

Back to Top

See other articles in Category Arrays