Jobs

Interviews

Discussions

Move Zeroes

Easy

Move Zeroes

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the `nums` array? Can they be negative?
What should happen if the input array `nums` is null or empty?
Besides integers, are there other data types that could appear in the `nums` array?
If the array contains only zeroes, what should the array look like after the operation?
By 'relative order of the non-zero elements', do you mean their original order in the input array must be completely preserved?

Brute Force Solution

Approach

The brute force method to move zeroes involves exhaustively checking each position in the list. It aims to create a new list where all the non-zero values appear first, followed by all the zeroes.

Here's how the algorithm would work step-by-step:

Create a separate, empty list to hold our rearranged values.
Go through the original list, one item at a time.
If the item is not a zero, put it at the end of the new list.
After you've checked every item in the original list, go through it again.
This time, if you find a zero, add it to the end of the new list.
The new list now contains all the non-zero items from the original list, in order, followed by all the zeroes.

Code Implementation

def move_zeroes_brute_force(original_list):
    new_list = []

    for element in original_list:
        # Add non-zero elements to the new list.
        if element != 0:
            new_list.append(element)

    # Add the zero elements to the new list
    for element in original_list:
        if element == 0:
            new_list.append(element)

    # Modify the original list in-place
    for index in range(len(original_list)): 
        original_list[index] = new_list[index]

    # The original list is now modified in-place
    return original_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of size n once to add non-zero elements to a new list. Then, it iterates through the same original list of size n again to add the zero elements to the new list. Therefore, the total number of operations is proportional to 2n. Thus the time complexity is O(n).

Space Complexity

O(N) – The provided algorithm creates a new list to store rearranged values. In the worst-case scenario, where the original list contains no zeroes, this new list will store all N elements from the original list before adding the zeroes at the end. Therefore, the auxiliary space used is directly proportional to the input size N, as the new list requires space to hold up to N elements. This leads to a space complexity of O(N).

Optimal Solution

Approach

The goal is to shift all the zeroes to the end while keeping the other numbers in the same order. We achieve this by focusing on the non-zero numbers and moving them to the front.

Here's how the algorithm would work step-by-step:

Imagine having two markers: one for where the next non-zero number should go, and another to look at each number in the original list.
Start with both markers at the beginning of the list.
As you move the second marker through the list, if you find a non-zero number, swap it with the number at the first marker's location. Then, move the first marker forward one spot.
The first marker always points to the next spot where a non-zero number needs to be placed. By swapping non-zero numbers into these positions, you ensure they stay in their relative order.
After the second marker has gone through the entire list, everything from the first marker to the end of the list will be zeroes. This is because all the non-zero numbers have been moved to the front.

Code Implementation

def move_zeroes(nums): 
    next_non_zero_position = 0
    
    # Iterate through the array to find non-zero elements.
    for current_index in range(len(nums)): 
        if nums[current_index] != 0:

            # Place the non-zero element at the next available position.
            nums[next_non_zero_position], nums[current_index] = nums[current_index], nums[next_non_zero_position]

            # Increment the index for the next non-zero position.
            next_non_zero_position += 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once using a single pointer. Inside the loop, it performs a swap operation when a non-zero element is encountered. The swap operation takes constant time. Therefore, the time complexity is directly proportional to the size of the input array n, resulting in O(n).

Space Complexity

O(1) – The algorithm described uses two markers (indices) to traverse and modify the input array in place. These markers, which are essentially integer variables, represent a fixed amount of extra memory. The space required for these markers does not depend on the size of the input array (N). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return immediately; in-place modification is trivial on an empty array.
Array with one element	Do nothing; the array is already trivially satisfying the condition.
Array with all zeroes	The 'insertion pointer' will stay at index 0, correctly placing all zeros at the end without changing the relative order.
Array with no zeroes	The 'insertion pointer' will increment to the end, leaving the array unchanged.
Array with leading zeros	The insertion pointer will move to the location of first non-zero and correctly swaps all non-zero elements to the front.
Array with trailing zeroes	The insertion pointer correctly points and swaps all non-zero elements to the front preserving original non-zero ordering.
Large array with many zeroes scattered throughout	The algorithm uses a single pass, making it efficient even for large arrays.
Array containing negative numbers along with zeroes	The algorithm works correctly because it only distinguishes between zero and non-zero elements, irrespective of sign.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the `nums` array? Can they be negative?
What should happen if the input array `nums` is null or empty?
Besides integers, are there other data types that could appear in the `nums` array?
If the array contains only zeroes, what should the array look like after the operation?
By 'relative order of the non-zero elements', do you mean their original order in the input array must be completely preserved?

Brute Force Solution

Approach

The brute force method to move zeroes involves exhaustively checking each position in the list. It aims to create a new list where all the non-zero values appear first, followed by all the zeroes.

Here's how the algorithm would work step-by-step:

Create a separate, empty list to hold our rearranged values.
Go through the original list, one item at a time.
If the item is not a zero, put it at the end of the new list.
After you've checked every item in the original list, go through it again.
This time, if you find a zero, add it to the end of the new list.
The new list now contains all the non-zero items from the original list, in order, followed by all the zeroes.

Code Implementation

def move_zeroes_brute_force(original_list):
    new_list = []

    for element in original_list:
        # Add non-zero elements to the new list.
        if element != 0:
            new_list.append(element)

    # Add the zero elements to the new list
    for element in original_list:
        if element == 0:
            new_list.append(element)

    # Modify the original list in-place
    for index in range(len(original_list)): 
        original_list[index] = new_list[index]

    # The original list is now modified in-place
    return original_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to shift all the zeroes to the end while keeping the other numbers in the same order. We achieve this by focusing on the non-zero numbers and moving them to the front.

Here's how the algorithm would work step-by-step:

Imagine having two markers: one for where the next non-zero number should go, and another to look at each number in the original list.
Start with both markers at the beginning of the list.
As you move the second marker through the list, if you find a non-zero number, swap it with the number at the first marker's location. Then, move the first marker forward one spot.
The first marker always points to the next spot where a non-zero number needs to be placed. By swapping non-zero numbers into these positions, you ensure they stay in their relative order.
After the second marker has gone through the entire list, everything from the first marker to the end of the list will be zeroes. This is because all the non-zero numbers have been moved to the front.

Code Implementation

def move_zeroes(nums): 
    next_non_zero_position = 0
    
    # Iterate through the array to find non-zero elements.
    for current_index in range(len(nums)): 
        if nums[current_index] != 0:

            # Place the non-zero element at the next available position.
            nums[next_non_zero_position], nums[current_index] = nums[current_index], nums[next_non_zero_position]

            # Increment the index for the next non-zero position.
            next_non_zero_position += 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return immediately; in-place modification is trivial on an empty array.
Array with one element	Do nothing; the array is already trivially satisfying the condition.
Array with all zeroes	The 'insertion pointer' will stay at index 0, correctly placing all zeros at the end without changing the relative order.
Array with no zeroes	The 'insertion pointer' will increment to the end, leaving the array unchanged.
Array with leading zeros	The insertion pointer will move to the location of first non-zero and correctly swaps all non-zero elements to the front.
Array with trailing zeroes	The insertion pointer correctly points and swaps all non-zero elements to the front preserving original non-zero ordering.
Large array with many zeroes scattered throughout	The algorithm uses a single pass, making it efficient even for large arrays.
Array containing negative numbers along with zeroes	The algorithm works correctly because it only distinguishes between zero and non-zero elements, irrespective of sign.