Strait-forward C++ solution with explanation.


  • 0

    The way is memorizing the most ahead "0" in the sequence (using 1 pointer : front) and do a scanning of the whole sequence (using another pointer : "i" in the for loop). Whenever a non-zero value is found, swap it with the ahead "0".

    class Solution {
        public:
            void moveZeroes(vector<int>& nums) {
                int front = -1;
                for(int i=0; i<nums.size(); ++i)
                {
                    if(nums[i] == 0)
                    {
                        if(front == -1) 
                            front = i;
                    }
                    else
                    {
                        if(front != -1)
                        {
                            swap(nums[i], nums[front]);
                            ++front;
                        }
                    }
                }
            }
        };
    

    The trick is why

     swap(nums[i], nums[front]);
      ++front;
    

    will work.
    The fact is that wherever the scanning pointer ("i") are, after the swap, the "front + 1" position will always be the next most ahead "0" in the sequence, whether there is or isn't any "0"s behind the first.


Log in to reply
 

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