Question

Formatted question description: https://leetcode.ca/all/283.html

 283. Move Zeroes

 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]

 Note:

 You must do this in-place without making a copy of the array.
 Minimize the total number of operations.

 @tag-array

Algorithm

To do in-place replacement method, you need to use two pointers, one of which keeps sweeping backwards to find a non-zero position, and then swap positions with the previous pointer.

Code

Java

public class Move_Zeroes {


    // time: O(N)
    // space: O(N)
    class Solution_swap {
        public void moveZeroes(int[] nums) {

            if (nums == null || nums.length == 0) {
                return;
            }

            int lastNonZeroAt = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    int tmp = nums[lastNonZeroAt];
                    nums[lastNonZeroAt] = nums[i];
                    nums[i] = tmp;

                    lastNonZeroAt++;
                }
            }
        }
    }

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

            int actualP = 0;
            int scanP = 0;

            while (scanP < nums.length) {

                if (nums[scanP] != 0) {
                    nums[actualP++] = nums[scanP++];
                } else {
                    scanP++;
                }

            }

            while (actualP < nums.length) {
                nums[actualP++] = 0;
            }
        }
    }


}

All Problems

All Solutions