Jobs

Interviews

Discussions

Move Zeroes

Easy

Asked by:

+23

More companies

311 views

Topics:

ArraysTwo Pointers

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⁴
-2³¹ <= nums[i] <= 2³¹ - 1

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

Try coding it in LeetCode

Move Zeroes

Easy

Asked by:

+17

More companies

311 views

Topics:

ArraysTwo Pointers

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⁴
-2³¹ <= nums[i] <= 2³¹ - 1

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

Try coding it in LeetCode

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 expected range of integer values in the `nums` array, and can it contain negative numbers?
Is the input array guaranteed to be non-null, and what should happen if it's empty?
Does the input array have any size constraints that I should be aware of (e.g., minimum or maximum number of elements)?
Are there any specific behaviors expected if the input array contains only zeros, or only non-zero elements?
While maintaining the relative order of non-zero elements is specified, are there any other implicit ordering requirements or preferences for the final arrangement of non-zero elements if multiple valid arrangements exist?

Brute Force Solution

Approach

The problem asks us to rearrange a collection of numbers so that all the non-zero numbers come first, followed by all the zeroes. The brute force approach involves considering every single possible arrangement of the numbers and picking the one that satisfies the condition.

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

Think about all the different ways you could possibly order the numbers in the collection.
For each of these different orderings, check if all the non-zero numbers appear before all the zero numbers.
If an ordering meets this requirement, consider it a valid solution.
After checking every single possible ordering, you will have a set of valid solutions.
Out of all the valid solutions you found, select one. In a brute force scenario, often the first one you discover is sufficient, or if there are multiple, you'd pick based on some secondary criteria if provided.

Code Implementation

import itertoolsdef move_zeroes_brute_force(list_of_numbers):    # Generating all possible permutations is necessary to explore every ordering.    for permutation_tuple in itertools.permutations(list_of_numbers):        permutation_list = list(permutation_tuple)                # We need to verify if the current arrangement satisfies the condition of non-zeroes first.        found_zero = False        is_valid_arrangement = True        for number in permutation_list:            if number == 0:                found_zero = True            elif found_zero:                # This condition ensures that once a zero is encountered, no non-zero can appear after it.                is_valid_arrangement = False                break                # If the arrangement meets the criteria, it's a valid solution and we can return it.        if is_valid_arrangement:            return permutation_list    # In the rare case no valid arrangement is found (e.g., if the input is empty), return an empty list.    return []

Big(O) Analysis

Time Complexity

O(n * n!) – The brute force approach considers all possible permutations of the input array of size n. The number of permutations for n distinct elements is n factorial (n!). For each of these n! permutations, we then need to iterate through the array to check if it satisfies the condition (all non-zeroes before zeroes). This check takes O(n) time. Therefore, the total time complexity is O(n * n!), which is extremely inefficient for larger input sizes.

Space Complexity

O(1) – The brute force approach, as described, explores all possible orderings of the input collection. This involves generating permutations. However, to *check* each permutation and identify valid solutions, we do not need to store all permutations simultaneously. We only need a few variables to keep track of the current permutation being examined and to count non-zero and zero elements. Therefore, the auxiliary space used is constant, irrespective of the input size N.

Optimal Solution

Approach

The most efficient way to solve this is by rearranging the existing items in place, treating it like a careful sorting process. We'll manage two conceptual points: one that keeps track of where the next non-zero item should go, and another that scans through all the items.

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

Imagine you have two markers. One marker points to the very beginning, and the other marker is going to sweep through all the items one by one.
As the sweeping marker encounters an item that isn't zero, you move that non-zero item to the position indicated by the first marker.
After moving the non-zero item, advance the first marker to the next spot.
Continue this process, moving all the non-zero items to the front of the collection.
Once all non-zero items have been moved to the front, everything from the position of the first marker to the end of the collection should be filled with zeroes.

Code Implementation

def move_zeroes(list_of_numbers):    next_non_zero_position_index = 0    # This index marks where the next non-zero element should be placed.    for current_scan_index in range(len(list_of_numbers)):        # If the current element is not zero, move it to the next non-zero position.        if list_of_numbers[current_scan_index] != 0:            list_of_numbers[next_non_zero_position_index] = list_of_numbers[current_scan_index]            next_non_zero_position_index += 1    # Fill the remaining positions from the next non-zero position to the end with zeroes.    # This ensures all zeroes are at the end of the list.    while next_non_zero_position_index < len(list_of_numbers):        list_of_numbers[next_non_zero_position_index] = 0        next_non_zero_position_index += 1

Big(O) Analysis

Time Complexity

O(n) – The solution involves a single pass through the input array of size n. The 'sweeping marker' iterates through each of the n elements exactly once. For each non-zero element encountered, a constant number of operations (assignment and increment) are performed. Therefore, the total number of operations is directly proportional to the number of elements, n. This leads to a linear time complexity of O(n).

Space Complexity

O(1) – The provided solution rearranges the elements in-place within the original array. It only utilizes a few constant-size variables to keep track of marker positions. These variables do not depend on the size of the input array, N. Therefore, the auxiliary space complexity is constant, O(1).

Edge Cases

Case	How to Handle
Null or empty input array	The function should gracefully handle null or empty arrays by doing nothing and returning immediately.
Array with a single element	An array with one element, whether zero or non-zero, requires no modification and should be returned as is.
Array with all zeros	If the array consists entirely of zeros, no elements need to be moved, and the array remains unchanged.
Array with no zeros	If the array contains no zeros, the relative order of non-zero elements is preserved, and no actual movement occurs.
Array with only one non-zero element	The single non-zero element should remain in its original relative position, followed by all the zeros.
Array with negative numbers and zeros	The algorithm should correctly distinguish between zero and negative non-zero numbers, maintaining their relative order.
Very large input array	The chosen in-place algorithm, typically using a two-pointer approach, has a time complexity of O(n) and space complexity of O(1), which scales efficiently for large inputs.
Array with maximum and minimum integer values	The algorithm should not be affected by the magnitude of the integer values as it only compares them to zero.

Null or empty input array

How to Handle:

The function should gracefully handle null or empty arrays by doing nothing and returning immediately.

Array with a single element

How to Handle:

An array with one element, whether zero or non-zero, requires no modification and should be returned as is.

Array with all zeros

How to Handle:

If the array consists entirely of zeros, no elements need to be moved, and the array remains unchanged.

Array with no zeros

How to Handle:

If the array contains no zeros, the relative order of non-zero elements is preserved, and no actual movement occurs.

Array with only one non-zero element

How to Handle:

The single non-zero element should remain in its original relative position, followed by all the zeros.

Array with negative numbers and zeros

How to Handle:

The algorithm should correctly distinguish between zero and negative non-zero numbers, maintaining their relative order.

Very large input array

How to Handle:

The chosen in-place algorithm, typically using a two-pointer approach, has a time complexity of O(n) and space complexity of O(1), which scales efficiently for large inputs.

Array with maximum and minimum integer values

How to Handle:

The algorithm should not be affected by the magnitude of the integer values as it only compares them to zero.

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 expected range of integer values in the `nums` array, and can it contain negative numbers?
Is the input array guaranteed to be non-null, and what should happen if it's empty?
Does the input array have any size constraints that I should be aware of (e.g., minimum or maximum number of elements)?
Are there any specific behaviors expected if the input array contains only zeros, or only non-zero elements?
While maintaining the relative order of non-zero elements is specified, are there any other implicit ordering requirements or preferences for the final arrangement of non-zero elements if multiple valid arrangements exist?

Brute Force Solution

Approach

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

Think about all the different ways you could possibly order the numbers in the collection.
For each of these different orderings, check if all the non-zero numbers appear before all the zero numbers.
If an ordering meets this requirement, consider it a valid solution.
After checking every single possible ordering, you will have a set of valid solutions.
Out of all the valid solutions you found, select one. In a brute force scenario, often the first one you discover is sufficient, or if there are multiple, you'd pick based on some secondary criteria if provided.

Code Implementation

import itertoolsdef move_zeroes_brute_force(list_of_numbers):    # Generating all possible permutations is necessary to explore every ordering.    for permutation_tuple in itertools.permutations(list_of_numbers):        permutation_list = list(permutation_tuple)                # We need to verify if the current arrangement satisfies the condition of non-zeroes first.        found_zero = False        is_valid_arrangement = True        for number in permutation_list:            if number == 0:                found_zero = True            elif found_zero:                # This condition ensures that once a zero is encountered, no non-zero can appear after it.                is_valid_arrangement = False                break                # If the arrangement meets the criteria, it's a valid solution and we can return it.        if is_valid_arrangement:            return permutation_list    # In the rare case no valid arrangement is found (e.g., if the input is empty), return an empty list.    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have two markers. One marker points to the very beginning, and the other marker is going to sweep through all the items one by one.
As the sweeping marker encounters an item that isn't zero, you move that non-zero item to the position indicated by the first marker.
After moving the non-zero item, advance the first marker to the next spot.
Continue this process, moving all the non-zero items to the front of the collection.
Once all non-zero items have been moved to the front, everything from the position of the first marker to the end of the collection should be filled with zeroes.

Code Implementation

def move_zeroes(list_of_numbers):    next_non_zero_position_index = 0    # This index marks where the next non-zero element should be placed.    for current_scan_index in range(len(list_of_numbers)):        # If the current element is not zero, move it to the next non-zero position.        if list_of_numbers[current_scan_index] != 0:            list_of_numbers[next_non_zero_position_index] = list_of_numbers[current_scan_index]            next_non_zero_position_index += 1    # Fill the remaining positions from the next non-zero position to the end with zeroes.    # This ensures all zeroes are at the end of the list.    while next_non_zero_position_index < len(list_of_numbers):        list_of_numbers[next_non_zero_position_index] = 0        next_non_zero_position_index += 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	The function should gracefully handle null or empty arrays by doing nothing and returning immediately.
Array with a single element	An array with one element, whether zero or non-zero, requires no modification and should be returned as is.
Array with all zeros	If the array consists entirely of zeros, no elements need to be moved, and the array remains unchanged.
Array with no zeros	If the array contains no zeros, the relative order of non-zero elements is preserved, and no actual movement occurs.
Array with only one non-zero element	The single non-zero element should remain in its original relative position, followed by all the zeros.
Array with negative numbers and zeros	The algorithm should correctly distinguish between zero and negative non-zero numbers, maintaining their relative order.
Very large input array	The chosen in-place algorithm, typically using a two-pointer approach, has a time complexity of O(n) and space complexity of O(1), which scales efficiently for large inputs.
Array with maximum and minimum integer values	The algorithm should not be affected by the magnitude of the integer values as it only compares them to zero.

Null or empty input array

How to Handle:

The function should gracefully handle null or empty arrays by doing nothing and returning immediately.

Array with a single element

How to Handle:

An array with one element, whether zero or non-zero, requires no modification and should be returned as is.

Array with all zeros

How to Handle:

If the array consists entirely of zeros, no elements need to be moved, and the array remains unchanged.

Array with no zeros

How to Handle:

If the array contains no zeros, the relative order of non-zero elements is preserved, and no actual movement occurs.

Array with only one non-zero element

How to Handle:

The single non-zero element should remain in its original relative position, followed by all the zeros.

Array with negative numbers and zeros

How to Handle:

The algorithm should correctly distinguish between zero and negative non-zero numbers, maintaining their relative order.

Very large input array

How to Handle:

The chosen in-place algorithm, typically using a two-pointer approach, has a time complexity of O(n) and space complexity of O(1), which scales efficiently for large inputs.

Array with maximum and minimum integer values

How to Handle:

The algorithm should not be affected by the magnitude of the integer values as it only compares them to zero.