This post is completed by 2 users

  • 1
 Add to List
Beginner

555. Move All Zeroes to the End of the Array

Problem Statement:

Given an array of random numbers, move all the zeros to the end of the array while maintaining the relative order of the non-zero elements.

Example 1:

Input: {0, 1, 0, 3, 12}
Output: {1, 3, 12, 0, 0}

Example 2:

Input: {1, 2, 0, 0, 3, 4}
Output: {1, 2, 3, 4, 0, 0}

Example 3:

Input: {0, 0, 0, 0}
Output: {0, 0, 0, 0}

Naive Solution:

  • Create a new result array of the same length as the input array.
  • Iterate through the input array and place each non-zero element in the result array.
  • Leave the zeroes at the end by default, as the uninitialized values in the result array are zeroes.

Time Complexity: O(N), Space Complexity: O(N)

 



import java.util.Arrays;

public class Main {

    public static void arrange(int [] input){

        System.out.println("Input: " + Arrays.toString(input));

        int [] result = new int[input.length];
        int index = 0;
        for (int i = 0; i < input.length; i++) {
            if(input[i]!=0){
                result[index++] = input[i];
            }
        }
        System.out.println("Output: " + Arrays.toString(result));
    }

    public static void main(String[] args) {
        int [] input = new int[] {0, 1, 0, 3, 12};
        arrange(input);
    }
}



def arrange(input_list):
    print("Input:", input_list)

    # Create a result array with the same length as the input
    result = [0] * len(input_list)
    index = 0

    # Move all non-zero elements to the front of the result array
    for num in input_list:
        if num != 0:
            result[index] = num
            index += 1

    print("Output:", result)

# Testing the function
input_list = [0, 1, 0, 3, 12]
arrange(input_list)

Output

[0, 1, 0, 3, 12] 
[1, 3, 12, 0, 0]

Better Solution:

  • Use a pointer (or counter) to track the position of non-zero elements.
  • Iterate through the array and shift all non-zero elements to the front.
  • Fill the remaining spaces with zeroes.

Time Complexity: O(N), Space Complexity: O(1)

 



public class Main {

    public static void arrange(int [] input){

        System.out.println("Input: " + Arrays.toString(input));

        int count = 0;
        for (int i = 0; i < input.length; i++) {
            if(input[i]!=0){
                input[count++] = input[i];
            }
        }

        // now put all zeros
        while(count<input.length){
            input[count++] = 0;
        }

        System.out.println("Output: " + Arrays.toString(input));
    }

    public static void main(String[] args) {
        int [] input = new int[] {1, 2, 0, 0, 3, 4};
        arrange(input);
    }
}



def arrange(input_list):
    print("Input:", input_list)

    count = 0  # Count for non-zero elements

    # Move all non-zero elements to the front
    for i in range(len(input_list)):
        if input_list[i] != 0:
            input_list[count] = input_list[i]
            count += 1

    # Fill the rest of the array with zeroes
    while count < len(input_list):
        input_list[count] = 0
        count += 1

    print("Output:", input_list)

# Testing the function
input_list = [1, 2, 0, 0, 3, 4]
arrange(input_list)

Output

Input: [1, 2, 0, 0, 3, 4]
Output: [1, 2, 3, 4, 0, 0]

Related Problems: