Keep and Share logo     Log In  |  Mobile View  |  Help  
 
Visiting
 
Select a Color
   
 












01.DS.02.06. Move All Zeros to the Beginning of the Array.html -- 1.7 meg
 Move All Zeros to the Beginning of the Array - Coderust: Hacking the Coding Interview
Log InJoin for free
Back To Module Home
Data Structures
0% completed
Prelude
Arrays
Move All Zeros to the Beginning of the Array
Linked Lists
Strings
Stacks and Queues
Trees
Graphs
Further Reading
Mark Module as Completed
Ask a Question

Move All Zeros to the Beginning of the Array

Move all zeros to the left of an array while maintaining its order.

We'll cover the following

Statement#

We’re given an integer array, nums. Move all zeroes if any to the left while maintaining the order of other elements in the array.

Example#

Let’s look at the following integer array:

garray01234567811020059630880

After moving all zeros to the left, the array should look like this:

garray01234567800011020596388

Note: We need to maintain the order of non-zero elements.

Sample input#

[1, 10, 20, 0, 59, 63, 0, 88, 0]

Expected output#

[0, 0, 0, 1, 10, 20, 59, 63, 88]

Try it yourself#

C++
Java
Python
JS
Ruby
Go
1
2
3
4
5
6
7
8
#include <iostream>
#include <vector>
using namespace std;
void MoveZerosToLeft(vector<int> &nums) {
    return;
}
#
#include <iostream> #include <vector> using namespace std; void MoveZerosToLeft(vector<int> &nums) { return; }
Enter to Rename, Shift+Enter to Preview
Test
Save
Reset

Solution#

We will use Read and Write pointers and start by pointing them to the end of the array. Let’s go over the algorithm.

While moving the Read pointer towards the start of the array:

  • If the value at the Read pointer is 0, decrement the Read pointer.
  • If the value at the Read pointer is non-zero, set the value at the Write pointer equal to the value at the Read pointer, and decrement the Write and Read pointers.
  • Once, the Read pointer reaches the 0th0^{th}0th index, start assigning zeros to all the values from the Write pointer back to the 0th0^{th}0th index.

The algorithm is visualized below:

Created with Fabric.js 3.6.6We will start from the last index of the array.Read01234567811020059630880Write
1 of 14
C++
Java
Python
JS
Ruby
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
using namespace std;
void MoveZerosToLeft(vector<int> &nums) {
    // Return if the list is empty
    int length_nums = nums.size();
    if (length_nums < 1) return;
    // Initializing the two markers
    int write_index = length_nums - 1;
    int read_index = length_nums - 1;
    // Iterate read_index marker till the index is less than or equal to 0
    while (read_index >= 0) {
        // Replacing write_index value with read_index value
        // This step moves the next non-zero value "back" in the array,
        // making space for the zero at the head of the array
        if (nums[read_index] != 0) {
            nums[write_index] = nums[read_index];
            write_index--;
        }
        read_index--;
    }
    // Replacing initial values with zeroes
    while (write_index >= 0) {
        nums[write_index] = 0;
        write_index--;
#
#include <iostream> #include <vector> using namespace std; void MoveZerosToLeft(vector<int> &nums) { // Return if the list is empty int length_nums = nums.size(); if (length_nums < 1) return;
Enter to Rename, Shift+Enter to Preview
Run
Save
Reset

Time complexity#

The time complexity of this solution is O(n)O(n)O(n).

Space complexity#

The space complexity of this solution is O(1)O(1)O(1).

Back
Find Low/High Index of a Key in a Sorted Array
Next
Stock Buy Sell to Maximize Profit
Mark as Completed
Report an Issue


Creation date: Oct 7, 2022 7:33pm     Last modified date: Oct 7, 2022 7:33pm   Last visit date: Nov 19, 2024 9:26am
    Report Objectionable Content