O(N) 0ms Java solution by swapping non-zero value to leftmost 0 value


  • 0
    T

    The idea is to iterate through the array and swap non-zero values with the leftmost zero value.
    Once an 0 is met, two cases can happen:

    1. following element is non-zero, then we swap the non-zero value with leftmost 0 value, and increment the position for leftmost zero by 1.
    2. following element is still 0, then we continue iterating until meeting a non-zero value and process as step 1).
      In either case, updating position of leftmost zero can be done by simply incrementing the index.
    public class Solution {
        public void moveZeroes(int[] nums) {
            if(nums.length<2)return;
            int first0 = -1, p=0;
            while(p<nums.length){
                if(nums[p]==0){ // we just met the first 0, record the position
                    if(first0<0)first0=p;
                }else{
                    if(first0>=0){ // we have one or more 0s right before current position
                        nums[first0++]=nums[p]; // swap current value with the leftmost 0 and increment the index of leftmost zero
                        nums[p]=0;
                    }
                }
                p++;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.