Skip to content

283. Move Zeroes

DifficultyEasy

Description

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 <= 104
  • -231 <= nums[i] <= 231 - 1

 

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

Solutions

Solution 1: Two Pointers

Thinking

Zeros must go to the end while nonzeros keep their order. Let \(k\) be the next slot for a nonzero.

Each nonzero is swapped with \(\textit{nums}[k]\) and \(k\) advances, so the prefix of length \(k\) is the original nonzero sequence.

We use a pointer \(k\) to record the current position to insert, initially \(k = 0\).

Then we iterate through the array \(\textit{nums}\), and each time we encounter a non-zero number, we swap it with \(\textit{nums}[k]\) and increment \(k\) by 1.

This way, we can ensure that the first \(k\) elements of \(\textit{nums}\) are non-zero, and their relative order is the same as in the original array.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        k = 0
        for i, x in enumerate(nums):
            if x:
                nums[k], nums[i] = nums[i], nums[k]
                k += 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] != 0) {
                int t = nums[i];
                nums[i] = nums[k];
                nums[k++] = t;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i]) {
                swap(nums[i], nums[k++]);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
func moveZeroes(nums []int) {
    k := 0
    for i, x := range nums {
        if x != 0 {
            nums[i], nums[k] = nums[k], nums[i]
            k++
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums: number[]): void {
    let k = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i]) {
            [nums[i], nums[k]] = [nums[k], nums[i]];
            ++k;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut k = 0;
        let n = nums.len();
        for i in 0..n {
            if nums[i] != 0 {
                nums.swap(i, k);
                k += 1;
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let k = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i]) {
            [nums[i], nums[k]] = [nums[k], nums[i]];
            ++k;
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void moveZeroes(int* nums, int numsSize) {
    int k = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != 0) {
            int t = nums[i];
            nums[i] = nums[k];
            nums[k++] = t;
        }
    }
}

Comments