Welcome to Subscribe On Youtube

Question

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

Given an integer array nums, 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 = [0]
Output: [0]

 

Constraints:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

 

Follow up: Could you minimize the total number of operations done?

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

  • 
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;
            }
        }
    }


}

############

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0, n = nums.length;
        for (int right = 0; right < n; ++right) {
            if (nums[right] != 0) {
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
                ++left;
            }
        }
    }
}

  • class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, n = 0, len(nums)
        for right in range(n):
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1

############

class Solution(object):
  def moveZeroes(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    i = j = 0
    for i in range(0, len(nums)):
      if nums[i] != 0:
        nums[j], nums[i] = nums[i], nums[j]
        j += 1


  • class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0, n = nums.size();
        for (int right = 0; right < n; ++right) {
            if (nums[right] != 0) {
                swap(nums[left], nums[right]);
                ++left;
            }
        }
    }
};

  • func moveZeroes(nums []int) {
	n := len(nums)
	left := 0
	for right := 0; right < n; right++ {
		if nums[right] != 0 {
			nums[left], nums[right] = nums[right], nums[left]
			left++
		}
	}
}


  • /**
 Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums: number[]): void {
    const n = nums.length;
    let i = 0;
    for (let j = 0; j < n; j++) {
        if (nums[j]) {
            if (j > i) {
                [nums[i], nums[j]] = [nums[j], 0];
            }
            i++;
        }
    }
}


  • /**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let left = 0,
        n = nums.length;
    for (let right = 0; right < n; ++right) {
        if (nums[right]) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            ++left;
        }
    }
};


  • impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut i = 0;
        for j in 0..nums.len() {
            if nums[j] != 0 {
                if j > i {
                    nums[i] = nums[j];
                    nums[j] = 0;
                }
                i += 1;
            }
        }
    }
}

All Problems

All Solutions