Jobs

Interviews

Discussions

Move Zeroes

Easy

Microsoft

3 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?

Move Zeroes

Easy

Microsoft

3 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?

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 I expect negative numbers?
What should happen if the input array `nums` is null or empty?
By 'maintaining the relative order of the non-zero elements', are you referring to preserving their original left-to-right sequence?
Could you clarify what the expected behavior is if all elements in the input array `nums` are zeroes?
Are there any memory constraints in addition to performing the operation in-place?

Brute Force Solution

Approach

The brute force way to solve this is to go through the list and whenever you find a zero, remember it. Then, shift all the non-zero numbers after it towards the front, one by one. Finally, put a zero at the end to cover for the shifted number.

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

Start at the beginning of the list.
Check if the current number is zero.
If it's not zero, move on to the next number and repeat the check.
If it is zero, remember its position.
Now, look at each of the following numbers, one at a time.
Move each of those numbers one position forward to fill in the zero's spot.
Once all the following numbers have been shifted, put a zero at the very end of the list.
Go back to where you left off checking for zeros and continue through the entire list, repeating this process until the end.

Code Implementation

def move_zeroes_brute_force(numbers):
    current_index = 0
    while current_index < len(numbers):
        if numbers[current_index] == 0:
            # Found a zero, shift subsequent elements
            index_to_shift_from = current_index + 1

            while index_to_shift_from < len(numbers):
                numbers[index_to_shift_from - 1] = numbers[index_to_shift_from]
                index_to_shift_from += 1

            # Place a zero at the end to replace shifted number
            numbers[len(numbers) - 1] = 0


        else:
            # Only increment if current element wasn't zero
            current_index += 1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the array of size n. When a zero is encountered, elements following it must be shifted forward. In the worst case, if the array consists of mostly zeros at the beginning, each zero would require shifting a large portion of the array. This shifting process, performed repeatedly for each zero found, results in nested iterations, approximating n * n/2 operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm description involves iterating through the input list and shifting elements in place. It only requires storing the position of the zero that was found, meaning a single index variable. No additional data structures like temporary lists or hash maps are created, and the recursion depth is not dependent on the input size. Therefore, the auxiliary space required is constant regardless of the input list's size N.

Optimal Solution

Approach

The goal is to shift all the zeroes to the end of a list while keeping the other numbers in the same order. We can solve this efficiently by using two different 'markers' that help us keep track of where to place the next non-zero number and what part of the list we've already processed.

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

Imagine you have two 'markers' or 'pointers', one that indicates where the next non-zero number should be placed (let's call it the 'placement marker') and another that is just walking through the entire list (let's call it the 'walker marker').
Start both markers at the beginning of the list.
As the 'walker marker' moves through the list, check the number it's currently looking at. If it's NOT zero, we have found a number that needs to be placed before the zeroes.
If the 'walker marker' finds a non-zero number, swap that number with the number at the 'placement marker's position.
After the swap, advance the 'placement marker' to the next position, since we've just filled its previous spot with a non-zero number.
The 'walker marker' always moves forward, checking every number in the list.
Once the 'walker marker' reaches the end of the list, all non-zero numbers will have been moved to the front, and all the zeroes will automatically be at the end.

Code Implementation

def move_zeroes(numbers):
    placement_marker = 0
    walker_marker = 0

    while walker_marker < len(numbers):
        # If current number is not zero,
        # it needs to be moved to the front.
        if numbers[walker_marker] != 0:

            numbers[placement_marker], numbers[walker_marker] = numbers[walker_marker], numbers[placement_marker]

            # Advance placement to the next available position.
            placement_marker += 1

        # Always move the walker marker forward
        walker_marker += 1

    return numbers

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input list of size n using the 'walker marker' exactly once. Inside the loop, it performs a swap operation in constant time if a non-zero element is encountered. The 'placement marker' also advances linearly. Therefore, the time complexity is directly proportional to the number of elements in the input list, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The described algorithm employs two pointers, 'placement marker' and 'walker marker', which are integer variables. The space required for these two pointers remains constant irrespective of the input list's size, denoted as N. No additional data structures, such as auxiliary arrays or hash maps, are allocated during the process. Therefore, the space complexity is O(1), indicating constant auxiliary space.

Edge Cases

Case	How to Handle
Null or empty input array	Return immediately or throw an IllegalArgumentException as appropriate for language conventions.
Array with only zeroes	The algorithm should still correctly place all zeroes at the end, leaving the array unchanged.
Array with no zeroes	The algorithm should leave the array unchanged, as all non-zero elements are already in the correct order.
Array with single element which is zero	Zero will remain at its single index.
Array with single element which is non-zero	Non-zero element will remain at its single index.
Array containing large numbers	The solution should handle potentially large numerical values without integer overflow as we are only swapping elements.
Array with alternating zero and non-zero values	The algorithm will iteratively swap the non-zero values to the front and push the zeroes to the back.
Large array size	The solution should have linear time complexity O(n), scaling efficiently with a large number of elements by minimizing unnecessary swaps.

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 I expect negative numbers?
What should happen if the input array `nums` is null or empty?
By 'maintaining the relative order of the non-zero elements', are you referring to preserving their original left-to-right sequence?
Could you clarify what the expected behavior is if all elements in the input array `nums` are zeroes?
Are there any memory constraints in addition to performing the operation in-place?

Brute Force Solution

Approach

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

Start at the beginning of the list.
Check if the current number is zero.
If it's not zero, move on to the next number and repeat the check.
If it is zero, remember its position.
Now, look at each of the following numbers, one at a time.
Move each of those numbers one position forward to fill in the zero's spot.
Once all the following numbers have been shifted, put a zero at the very end of the list.
Go back to where you left off checking for zeros and continue through the entire list, repeating this process until the end.

Code Implementation

def move_zeroes_brute_force(numbers):
    current_index = 0
    while current_index < len(numbers):
        if numbers[current_index] == 0:
            # Found a zero, shift subsequent elements
            index_to_shift_from = current_index + 1

            while index_to_shift_from < len(numbers):
                numbers[index_to_shift_from - 1] = numbers[index_to_shift_from]
                index_to_shift_from += 1

            # Place a zero at the end to replace shifted number
            numbers[len(numbers) - 1] = 0


        else:
            # Only increment if current element wasn't zero
            current_index += 1

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' or 'pointers', one that indicates where the next non-zero number should be placed (let's call it the 'placement marker') and another that is just walking through the entire list (let's call it the 'walker marker').
Start both markers at the beginning of the list.
As the 'walker marker' moves through the list, check the number it's currently looking at. If it's NOT zero, we have found a number that needs to be placed before the zeroes.
If the 'walker marker' finds a non-zero number, swap that number with the number at the 'placement marker's position.
After the swap, advance the 'placement marker' to the next position, since we've just filled its previous spot with a non-zero number.
The 'walker marker' always moves forward, checking every number in the list.
Once the 'walker marker' reaches the end of the list, all non-zero numbers will have been moved to the front, and all the zeroes will automatically be at the end.

Code Implementation

def move_zeroes(numbers):
    placement_marker = 0
    walker_marker = 0

    while walker_marker < len(numbers):
        # If current number is not zero,
        # it needs to be moved to the front.
        if numbers[walker_marker] != 0:

            numbers[placement_marker], numbers[walker_marker] = numbers[walker_marker], numbers[placement_marker]

            # Advance placement to the next available position.
            placement_marker += 1

        # Always move the walker marker forward
        walker_marker += 1

    return numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return immediately or throw an IllegalArgumentException as appropriate for language conventions.
Array with only zeroes	The algorithm should still correctly place all zeroes at the end, leaving the array unchanged.
Array with no zeroes	The algorithm should leave the array unchanged, as all non-zero elements are already in the correct order.
Array with single element which is zero	Zero will remain at its single index.
Array with single element which is non-zero	Non-zero element will remain at its single index.
Array containing large numbers	The solution should handle potentially large numerical values without integer overflow as we are only swapping elements.
Array with alternating zero and non-zero values	The algorithm will iteratively swap the non-zero values to the front and push the zeroes to the back.
Large array size	The solution should have linear time complexity O(n), scaling efficiently with a large number of elements by minimizing unnecessary swaps.