Reordering numbers in an array

Question

I am trying to solve a leetcode problem :

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0]

And I think I have the correct solution but I'm just not sure why I'm getting it incorrect.

class Solution {
    public void moveZeroes(int[] nums) {
        for (int i = 0; i > nums.length;i++) {
            int j= i;
            while ((j<nums.length) && (nums[j]==0)){
                j++;
            }
            if (j<nums.length){
                nums[i]=nums[j];
                nums[j]=0;
            }
        }
        
    }
}

`i > nums.length` in for-loop. That makes to never execute for-loop. It should be `i < nums.length` — KunLun, Jul 09 '20 at 15:13
This is a partition problem, you can try a generic partition solution which might make the code more concise, for example: https://stackoverflow.com/a/46958064/5698534 — Erez Ben Harush, Jul 09 '20 at 15:47

score 3 · Answer 1 · answered Jul 09 '20 at 15:21

You can solve this problem O(N) with one pointer. This'd pass through:

public class Solution {
    public static void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0)
            return;

        int pos = 0;
        for (int num : nums)
            if (num != 0)
                nums[pos++] = num;
        while (pos < nums.length)
            nums[pos++] = 0; 
    }
}

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

The result is the same but you're not *moving* the zeroes as the task implies. You're just copying non-zeroes to the front and then inserting 0's at the end. — WJS, Jul 09 '20 at 15:39

score 1 · Answer 2 · answered Jul 09 '20 at 15:22

The for loop isn't correct (has to be i < nums.length), also, your solution doesn't work if there is nothing to do:

    final int[] expectedArray = {1,2,0,0};
    final String expectedString = Arrays.toString(expectedArray);
    
    int[] nothingToDo = {1,2,0,0};
    moveZeroes(nothingToDo);
    assertEquals(expectedString, Arrays.toString(nothingToDo));

yields in:

org.junit.ComparisonFailure: expected:<[[1, 2], 0, 0]> but was:<[[0, 0], 0, 0]>

Just write some test cases yourself and see what's wrong.

In your case:

    if (j<nums.length){
            nums[i]=nums[j];
            nums[j]=0;
        }

is wrong because you're swapping i with j, even if i == j and nums[i] != 0.

Since I don't think you're asking for a working solution, I won't provide one. But here are my test cases:

@Test
public void testEmptyArray() {
    int[] array = new int[0];
    moveZeroes(array);
    assertEquals(0,array.length);
}

@Test
public void testZeroOnlyArrays() {
    int[] array = {0,0,0,0};
    final String arrayString = Arrays.toString(array);
    moveZeroes(array);
    assertEquals(arrayString, Arrays.toString(array));;
}

@Test
public void mixedTest() {
    
    int[] array = {0,1,0,2};
    final int[] expectedArray = {1,2,0,0};
    final String expectedString = Arrays.toString(expectedArray);
    moveZeroes(array);
    assertEquals(expectedString, Arrays.toString(array));;
    
    int[] nothingToDo = {1,2,0,0};
    moveZeroes(nothingToDo);
    assertEquals(expectedString, Arrays.toString(nothingToDo));
}

score 0 · Answer 3 · answered Jul 09 '20 at 15:15

The 'for' loop should be: for (int i = 0; i < nums.length;i++) then, your loop will run on the array indexes from 0 until it reaches the length of the array.

The current code will not even enter the loop as you have defined i=0 and the loop condition is run the loop only if it is larger than the array size: (i > nums.length) which of course is not true

Eklavya · Answer 4 · 2020-07-09T15:34:36.450

You are using i > nums.length that's why loop is not executed

You need an index for non-zero value. Here in my solution j is for non-zero value index means when you find a non-zero value set j index and increment it. If j is smaller than i or equal that's means there will be zero found then set it.

  public void moveZeroes(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] != 0) {
        nums[j] = nums[i];
        j++;
      }
      if (j <= i) {
        nums[i] = 0;
      }
    }
  }

Reordering numbers in an array

4 Answers4

References