Simple and Fast Java solution (no swap, one pointer)


  • 0
    S

    In this solution, we always move non-zero items to the left. There is a pattern in how many steps you should move a non-zero item to the left. Let's take the input array from the question as an example

    nums  = [ 0  1  0  3  12 ]
    delta = [ _  1  _  2  2  ] 
    

    The delta array is only for illustration purpose. We don't actually create it. delta[i] is the number of zeros on the left of i. Thus, delta[1] is 1, because there is only one zeros to its left. delta[3] is 2, because there are two zeros to its left. The same applies to delta[4].

    Notice that delta[i] also indicates how many steps we should left-move nums[i], i.e., we should move nums[i] to the position i - delta[i] in the array. For example, 3 should be moved to position 1, because its current index is 3, and its delta is 2.

    public void moveZeroes(int[] nums) {
        int num0s = 0; 
        
        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];
            // If we see 0, we increase the number of 0s we've seen.
            if (v == 0) num0s += 1;
            else {
                // If we see a non-0, we left-move the current item, 
                // using the fact that num0s is the number of steps 
                // we should left-move.
                if (num0s > 0) {
                    int targetIdx = i - num0s;
                    nums[targetIdx] = v;
                    nums[i] = 0;
                }
            }
        }
       
    }
    

Log in to reply
 

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