0283. Move Zeroes

Easy | Array + Two Pointers | 160 ms (93.57%), 15.3 MB (90.82%)

❓ Problem Statement

Source: LeetCode - Move Zeroes GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 1 <= nums.length <= 10^4

• -2^31 <= nums[i] <= 2^31 - 1

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Input: nums = [0]
Output: [0]

💡 Ideas

Two pointers: one is for placing non-zero numbers (since we need to move zero to the end), the other one is for iterating from the beginning.

Whenever move-pointer meets the non-zero integer, we swap it with the element pointed by the place-pointer, which is initialized at the index 0.

Also, for each iteration, we move the place-pointer by increasing its index when we perform a swap operation.

🤖 Python3

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        #  (base case)
        if len(nums) == 1: return
        
        # ==================================================
        #  Array + Two Pointer                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        placeP, moveP = 0, 0
        
        while moveP < len(nums):
            if nums[moveP] != 0: 
                nums[placeP], nums[moveP] = nums[moveP], nums[placeP]
                placeP += 1
            
            moveP += 1

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */
    
    public void moveZeroes(int[] nums) {
        /* base case */
        if(nums.length == 1) return;
        
        int moveP = 0, placeP = 0;
        
        while(moveP < nums.length) {
            if(nums[moveP] != 0) {
                /* swap */
                int tmp = nums[placeP];
                nums[placeP] = nums[moveP];
                nums[moveP] = tmp;
                
                placeP += 1;
            }
            
            moveP += 1;
        }
    }
}