C++, in place, no swap, clean O(n) solution with explanations


  • 1
    J

    Refer to the comments. Happy to share my first attempt Accepted solution :)
    I used "Counting Sort" idea and tried to make code easy to understand.

    void moveZeroes(vector<int>& nums) {
            
            int index=0;
            int zcount=0;
            
            // let's count the number of 0 and move all non-0 to their final positions (to track that position I use index)
            for(auto it = nums.begin(); it != nums.end(); ++it){
                if(*it == 0)
                    ++zcount;        
                else 
                    nums[index++] = *it;
            }
            // we are done here with moving all non-0 to their positions
            // we know the last position in the array where 0s should start from - index
            // also, we know the number of 0s in the array - zcount 
            
            // let's put all 0s in there places here
            while(index < nums.size())
                nums[index++]=0;
            
        }
    

    Update according to comments from ftbmynameis

    void moveZeroes(vector<int>& nums) {
        
        int index=0;
        int N = nums.size();
    
        for(int i = 0; i < N; ++i){
            if(nums[i] != 0){
                if(i != index){
                    nums[index] = nums[i];
                    nums[i]=0;
                }
                
                ++index;
            }
        }
    }

  • 0
    F

    Well, there definetly is an easier solution to this using only 1 for loop and in O(n).
    Technically with a solution containing a lot / only 0's your solution would run in almost O(2n) (which is still in O(n) but it is definetly doable in "real" O(n))

    Also you don't use your zcount var, so there is no need for it.


  • 0
    J

    True :) so funny I did not notice it ;)


  • 0
    V

    I doubt that this judgement, 'if(i != index)', is necessary. It is only useful in one case and mostly it is a waste of time.


Log in to reply
 

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