Python, simple solution, invariant explained breifly

  • 0

    The variable z keeps track of the number of zeros seen so far. With this variable at anytime is is safe to conclude the number at position i-z is the leftmost zero in the array. When the number at position i is a non-zero, swap with i-z. If the number at position i is a zero increase z by one and continue.

    Invariant (indices are [inclusive: not inclusive]) :
    nums[:i-z] := no zeros
    nums[i-z:i] := all zeros
    nums[i:] := not processed yet

    def moveZeroes(self, nums):
        z = 0 # track number of zeros
        for i in xrange(len(nums)):
            if nums[i] == 0:
                z += 1
                nums[i], nums[i-z] = nums[i-z], nums[i]

    I am aware of similar solutions. Although, I have not seen this explicit strategy used.

Log in to reply

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