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