Algorithm gymnastics 7

Move zeros to left

Description

An array of integer type is passed. Let's implement an algorithm that moves all elements equal to 0 to the left while maintaining the order of the other elements in the array. Let's take a look at the following integer array.

Moving all zero-equal elements to the left, the array looks like this: (Must keep the order of non-zero elements)

Solution

Runtime Complexity O(n) You need to find the 0 element in the array. Memory Complexity O(1) It can be implemented only with the array passed by using two pointers (iterators).

The main flow of the algorithm is

1. Place the two markers read_index and write_index on the last element of the array. <img width = "593" alt = "Screen Shot 2019-12-20 at 17.57.38.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/4eb6fef7-29d6-0684-1a39-91df7a6d3f80.png ">

2. While read_index is 0 or greater

3. If read_index points to "0", decrement only read_index. <img width = "594" alt = "Screen Shot 2019-12-20 at 17.58.40.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/e6fc1c0e-cc76-b5b6-44f7-764ead2af83a.png "> If read_index points to a non-zero value, write an element of read_index to write_index and decrement both write_index and read_index. <img width = "564" alt = "Screen Shot 2019-12-20 at 17.59.59.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/6b20aea1-b27b-2a3d-344d-dee0eda0c1d4.png ">

4. read_index becomes -1, exit the loop, and assign the elements of the array to 0 from the current write_index to 0.

5. Completion

Implementation

moveZeroToLeft.java

public class moveZerosToLeft {
    public void move_zeros_to_left_in_array(int[] A) {

        int readIndex = A.length - 1;
        int writeIndex = A.length -1;

        while (readIndex >= 0) {

            if (A[readIndex] != 0) {
                A[writeIndex] = A[readIndex];
                writeIndex--;
            }
            readIndex--;
        }

       while (writeIndex >= 0) {
           A[writeIndex] = 0;
           writeIndex--;
       }
    }
}

Mina.java

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // write your code here
        moveZerosToLeft algorithm = new moveZerosToLeft();

        int[] v = new int[]{1, 10, -1, 11, 5, 0, -7, 0, 25, -35};
        System.out.println("Original Array: " + Arrays.toString(v));
        algorithm.move_zeros_to_left_in_array(v);
        for (int item : v) {
            System.out.print(item + ", ");
        }
    }
}

Output