Python solution (linear time, and constant space) with explanation


  • 1
    # linear time, and constant space complexity
    def moveZeroes(self, nums):
        zero_i = nonzero_i = 0
        while zero_i <= nonzero_i and zero_i < len(nums) and nonzero_i < len(nums):
            nums[zero_i], nums[nonzero_i] = nums[nonzero_i], nums[zero_i]
            while zero_i < len(nums) and nums[zero_i] != 0:
                zero_i += 1
            while nonzero_i < len(nums) and nums[nonzero_i] == 0:
                nonzero_i += 1
            while zero_i > nonzero_i:
                nonzero_i += 1
    

    Explanation: Find the index with a zero number, find the index with a non-zero number, and swap them. The last while loop deals with an edge case where the zero number index gets ahead of the non-zero index, but there might be more numbers that need to be swapped later. An example of this is: [1,3,0,3,8,0,0,12,2]


Log in to reply
 

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