Skip to main content

Move Zeroes to end of Array in Java | LeetCode problem

Java code for Move All Zeroes to end of given Array without creating new Array with explanation

Problem Description :-

Given an integer array, 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 = [1, 0, 0, 5, 6, 9, 0]
Output: [1, 5, 6, 9, 0, 0, 0]

Solution 1

class Solution {
    
    public void moveZeroes(int[] array) {
        
        // Traverse array from left to right
        for (int i = 0; i < array.length-1; i++) {
           
            // Check if current element is 0 or not.
            if (array[i] == 0) {
               
                // If current element is 0 then again traverse array
                // From i+1 to last array element
                for (int j = i+1; j < array.length; j++) {

                    // If next element is non 0,
                    // then swap j index element to i index and break inner loop.
                    if (array[j] != 0) {
                        array[i] = array[j];
                        array[j] = 0;
                        break;
                    }
                }
            }
        }
    }
}

Explanation :-

array =  [0, 1, 0, 3, 12]

  • Outer for loop. i = 0, array = [0, 1, 0, 3, 12]
    • array[0] == 0 becomes true.
    • Inner for loop. j = 1
      • array[1] != 0 becomes true.
      • Swap array[0] = array[1] and assign array[1] = 0. 
      • array = [1, 0, 0, 3, 12]
      • Break inner loop.
  •  i = 1, array = [1, 0, 0, 3, 12]
    • array[1] == 0 becomes true.
    • Inner for loop. j = 2
      • array[2] != 0 becomes false.
    • j = 3
      • array[3] != 0 becomes false.
      • Swap array[1] = array[3] and assign array[3] = 0. 
      • array = [1, 3, 0, 0, 12]
      • Break inner loop.
  • i = 2, array = [1, 3, 0, 0, 12]
    • array[2] == 0 becomes true.
    • Inner for loop. j = 3
      • array[3] != 0 becomes false.
    • j = 4
      • array[4] != 0 becomes false.
      • Swap array[2] = array[4] and assign array[4] = 0. 
      • array = [1, 3, 12, 0, 0]
      • Break inner loop.
  • i = 3, array = [1, 3, 12, 0, 0]
    • array[3] == 0 becomes true.
    • Inner for loop. j = 4
      • array[4] != 0 becomes false.
  • i = 4. condition becomes false in for loop and we got final array as below.
  • array = [1, 3, 12, 0, 0]

Solution 2

class Solution {
    
    public void moveZeroes(int[] array) {
        
        int lastNonZeroIndex = 0;
for (int i = 0; i < array.length; i++) {
    if (array[i] != 0) {
        array[lastNonZeroIndex++] = array[i];
    }
}

for (int i = lastNonZeroIndex; i < array.length; i++) {
    array[i] = 0;
}
    }
}

Explanation :-

  • Define int variable and assign value 0.
  • Traverse array from left to right.
  • If current element is non zero, then assign at lastNonZeroIndex variable index.
  • In second for loop, put all 0 at end of array.

Solution Explanation :-

array =  [0, 1, 0, 3, 12]

  • First For Loop
  • i = 0, lastNonZeroIndex = 0
    • array[0] != 0 becomes false.
  • i = 1, lastNonZeroIndex = 0
    • array[1] != 0 becomes true.
    • array[0] = array[1]
    • array = [1, 1 ,0, 3, 12]
  • i = 2, lastNonZeroIndex = 1
    • array[2] != 0 becomes false.
  • i = 3, lastNonZeroIndex = 1
    • array[3] != 0 becomes true.
    • array[1] = array[3]
    • array = [1, 3 ,0, 3, 12]
  • i = 4, lastNonZeroIndex = 2
    • array[4] != 0 becomes true.
    • array[2] = array[4]
    • array = [1, 3 ,12 , 3, 12]
  • i = 5, lastNonZeroIndex = 3

  • Second For Loop
  • i = lastNonZeroIndex | i = 3
    • array[3] = 0
  • i = 4
    • array[4] = 0
  • array = [1, 3, 12, 0, 0]

 

Happy Coding.

Other articles you may like :-

Comments

Popular posts from this blog

Flipping the Matrix HackerRank Solution in Java with Explanation

Java Solution for Flipping the Matrix | Find Highest Sum of Upper-Left Quadrant of Matrix Problem Description : Sean invented a game involving a 2n * 2n matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times. The goal of the game is to maximize the sum of the elements in the n *n submatrix located in the upper-left quadrant of the matrix. Given the initial configurations for q matrices, help Sean reverse the rows and columns of each matrix in the best possible way so that the sum of the elements in the matrix's upper-left quadrant is maximal.  Input : matrix = [[1, 2], [3, 4]] Output : 4 Input : matrix = [[112, 42, 83, 119], [56, 125, 56, 49], [15, 78, 101, 43], [62, 98, 114, 108]] Output : 119 + 114 + 56 + 125 = 414 Full Problem Description : Flipping the Matrix Problem Description   Here we can find solution using following pattern, So simply we have to find Max of same number of box like (1,1,1,1). And ...

How to Implement One to Many and Many to One Mapping in Spring Boot using JPA

Spring Boot CRUD example using One-to-Many and Many to One mapping | With Thymeleaf User Interface In this tutorial, we will learn how to use @OneToMany and @ManyToOne annotation using JPA (Java Persistent API) in Spring Boot. We also attach Thymeleaf for User Interface. In past tutorial, we already created Spring Boot CRUD with Rest API, JPA and MySql. Please refer that one first, we will continue from there. Spring Boot application with Thymeleaf, Rest API, JPA and MySql Database    For applying One to Many relationship, we need another POJO class. In past we already created Book class, now we will create new class Author . As we know Author have multiple Books, so we can easily apply One to Many operation. Lets create POJO class for Author and apply @OneToMany on Book .  Define List of Book and apply @OneToMany annotation on field. We are using mappedBy property, so Author table does not create new column.  We already learn about mappedBy property in One-to-One a...