283. Move Zeroes

Description of Problem

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you minimize the total number of operations done?

Solution 1

Tags: Two Pointers Turing Machine

Explanation

Code

impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let n = nums.len();
        let (mut read_head, mut write_head, mut count_zeros) = (0, 0, 0);
        while read_head < n {
            if nums[read_head] != 0 {
                nums[write_head] = nums[read_head];
                write_head += 1;
            }
            read_head+=1;
        }

        while write_head < n {
            nums[write_head] = 0;
            write_head += 1;
        }
    }
}

Complexity

n is length of nums

Time Complexity

\( T(n)= O(n) \)

Auxiliary Space

\( S(n)= O(1) \)

Solution 2

Tags: Two Pointers

Explanation

The solution is provided by LeetCode official. When nums[read_head] is non-zero, swap it and nums[write_head], the following loop invariant verify the correctness of the above method.

Loop invariant (non-inclusive range):

write_head <= read_head
nums[write_head..read_head] are all zeros
nums[..write_head] are all non-zeros

Code

impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let n = nums.len();
        let (mut read_head, mut write_head) = (0, 0);
        while read_head < n {
            if nums[read_head] != 0 {
                let temp = nums[write_head];
                nums[write_head] = nums[read_head];
                nums[read_head] = temp;
                write_head += 1;
            }
            read_head+=1;
        }
    }
}

Complexity

n is length of nums

Time Complexity

\( T(n)= O(n) \)

Auxiliary Space

\( S(n)= O(1) \)

Leetbook