# LeetCode Solution, Easy, 283. Move Zeroes

# [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)

## 題目敘述

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?

**Hint 1**

**In-place** means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

**Hint 2**

A **two-pointer** approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

### 題目翻譯

有個整數陣列 `nums`，需要將其中為 `0` 的元素往後挪移。而其他非 `0` 的數值需要保持其排序。必須使用 In-place 的方式來解答，可以嘗試利用 two-pointer 來降低複雜度。

## 解法解析

官方提供了三種解法，當然解法不止這三種，不同語言也有不同的特性或語法糖可以使用。可以各自變化，這邊只是解釋三種解法的解題思路。

### Space Sub-Optimal

分成幾個步驟：

1. 先用一層迴圈找出 `0` 的數量 `numZeroes`。`O(n)`
2. 跑一層迴圈只出非 `0` 的元素，放到另一個陣列 `arr`。Worest case：`O(n)` 全部都非 `0`
3. 跑一層迴圈將在第一步驟求出的 `0` 數量，放到 `arr` 中。Worest case：`O(n)` 全部都是 `0`
4. 將 `arr` 的值都轉換到 `nums`。`O(n)`

時間複雜度：`O(n)`，`O(4n) => O(n)`

空間複雜度：`O(n)`

### Space Optimal, Operation Sub-Optimal

使用 two-pointer 的方式，一個去記上次 `0` 值的位置，一個是目前遍歷的索引位置。

1. 第一個迴圈將所有的非 `0` 值往前放，用 `lastNonZeroFoundAt` 紀錄目前最後出現的 `0` 在哪個位置。
2. 從 `lastNonZeroFoundAt` 的位置到結尾都直接設定為 `0`

時間複雜度：`O(n)`

空間複雜度：`O(1)`

### Optimal

這題跟上一個解法的 two-pointer 概念相同，只是這邊利用 Swap 的方式，將兩個迴圈合併成一個。

時間複雜度：`O(n)`

空間複雜度：`O(1)`

### 解法範例

#### Go

##### Space Sub-Optimal

```go
func moveZeroes(nums []int) {
	var n, numZeroes int = len(nums), 0
	for i := 0; i < n; i++ {
		if nums[i] == 0 {
			numZeroes++
		}
	}
	var ans []int
	for _, num := range nums {
		if num != 0 {
			ans = append(ans, num)
		}
	}
	for numZeroes > 0 {
		ans = append(ans, 0)
		numZeroes--
	}
	for i := 0; i < n; i++ {
		nums[i] = ans[i]
	}
}
```

##### Space Optimal, Operation Sub-Optimal

```go
func moveZeroes(nums []int) {
	var lastNonZeroFoundAt int = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[lastNonZeroFoundAt] = nums[i]
			lastNonZeroFoundAt++
		}
	}
	for i := lastNonZeroFoundAt; i < len(nums); i++ {
		nums[i] = 0
	}
}
```

##### Optimal

```go
func moveZeroes(nums []int) {
	var lastNonZeroFoundAt int = 0
	for i, num := range nums {
		if num != 0 {
			nums[lastNonZeroFoundAt], nums[i] = num, nums[lastNonZeroFoundAt]
			lastNonZeroFoundAt++
		}
	}
}
```

#### JavaScript

##### Space Sub-Optimal

```javascript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    const n = nums.length;
    let numZeroes = 0;
    for (let i = 0; i < n; i++) {
        numZeroes += nums[i] === 0 ? 1 : 0;
    }

    const ans = [];
    for (const num of nums) {
        if (num !== 0) {
            ans.push(num);
        }
    }
    while (numZeroes--) {
        ans.push(0);
    }
    nums.splice(0, nums.length, ...ans);
};
```

##### Space Optimal, Operation Sub-Optimal

```javascript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let lastNonZeroFoundAt = 0;
    for (const num of nums) {
        if (num !== 0) {
            nums[lastNonZeroFoundAt++] = num;
        }
    }
    while (lastNonZeroFoundAt < nums.length) {
        nums[lastNonZeroFoundAt++] = 0;
    }
};
```

##### Optimal

```javascript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let lastNonZeroFoundAt = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            [nums[lastNonZeroFoundAt], nums[i]] = [nums[i], nums[lastNonZeroFoundAt]];
            lastNonZeroFoundAt++;
        }
    }
};
```

#### Kotlin

##### Space Sub-Optimal

Kotlin 的 Array 太多樣了，不太熟悉，所以就沒寫了

```kotlin
```

##### Space Optimal, Operation Sub-Optimal

```kotlin
class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var lastNonZeroFoundAt = 0

        for (num in nums) {
            if (num != 0) {
                nums[lastNonZeroFoundAt++] = num
            }
        }

        for (i in lastNonZeroFoundAt until nums.size) {
            nums[i] = 0
        }
    }
}
```

##### Optimal

```kotlin
class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var lastNonZeroFoundAt: Int = 0
        for (i in nums.indices) {
            if (nums[i] != 0) {
                nums[lastNonZeroFoundAt] = nums[i].also { nums[i] = nums[lastNonZeroFoundAt] }
                lastNonZeroFoundAt++
            }
        }
    }
}
```

#### PHP

##### Space Sub-Optimal

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums)
    {
        $n = count($nums);

        $numZeroes = 0;
        for ($i = 0; $i < $n; $i++) {
            if ($nums[$i] == 0) {
                $numZeroes++;
            }
        }

        $ans = array();
        foreach ($nums as $num) {
            if ($num != 0) {
                $ans[] = $num;
            }
        }

        while ($numZeroes > 0) {
            $ans[] = 0;
            $numZeroes--;
        }

        for ($i = 0; $i < $n; $i++) {
            $nums[$i] = $ans[$i];
        }
    }
}
```

##### Space Optimal, Operation Sub-Optimal

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums)
    {
        $lastNonZeroFoundAt = 0;
        foreach($nums as $num) {
            if ($num != 0) {
                $nums[$lastNonZeroFoundAt++] = $num;
            }
        }
        while ($lastNonZeroFoundAt < count($nums)) {
            $nums[$lastNonZeroFoundAt++] = 0;
        }
    }
}
```

##### Optimal

```php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums)
    {
        $lastNonZeroFoundAt = 0;
        for ($i = 0; $i < count($nums); $i++) {
            if ($nums[$i] != 0) {
                $tmp = $nums[$lastNonZeroFoundAt];
                $nums[$lastNonZeroFoundAt] = $nums[$i];
                $nums[$i] = $tmp;
                $lastNonZeroFoundAt++;
            }
        }
    }
}
```

#### Python

##### Space Sub-Optimal

```python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        # Count the zeroes
        num_zeroes = 0
        for i in range(n):
            num_zeroes += nums[i] == 0

        # Make all the non-zero elements retain their original order.
        ans = list()
        for num in nums:
            if num != 0:
                ans.append(num)

        # Move all zeroes to the end
        while num_zeroes > 0:
            ans.append(0)
            num_zeroes -= 1

        # Combine the result
        for i in range(n):
            nums[i] = ans[i]
```

##### Space Optimal, Operation Sub-Optimal

```python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        last_non_zero_found_at = 0
        # If the current element is not 0, then we need to
        # append it just in front of last non 0 element we found.
        for num in nums:
            if num != 0:
                nums[last_non_zero_found_at] = num
                last_non_zero_found_at += 1

        # After we have finished processing new elements,
        # all the non-zero elements are already at beginning of array.
        # We just need to fill remaining array with 0's.
        for i in range(last_non_zero_found_at, len(nums)):
            nums[i] = 0
```

##### Optimal

```python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        last_non_zero_found_at = 0
        for (i, num) in enumerate(nums):
            if num != 0:
                nums[last_non_zero_found_at], nums[i] = (
                    nums[i],
                    nums[last_non_zero_found_at],
                )
                last_non_zero_found_at += 1
```

#### Rust

```rust
```

#### Swift

##### Space Sub-Optimal

```swift
class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        let n: Int = nums.count

        var numZeroes: Int = 0
        for i in 0..<n {
            if nums[i] == 0 {
                numZeroes += 1
            }
        }

        var ans: [Int] = []
        for num in nums {
            if num != 0 {
                ans.append(num)
            }
        }

        while numZeroes > 0 {
            ans.append(0)
            numZeroes -= 1
        }

        nums = ans
    }
}
```

##### Space Optimal, Operation Sub-Optimal

```swift
class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var lastNonZeroIndex: Int = 0
        for num in nums {
            if num != 0 {
                nums[lastNonZeroIndex] = num
                lastNonZeroIndex += 1
            }
        }

        while lastNonZeroIndex < nums.count {
            nums[lastNonZeroIndex] = 0
            lastNonZeroIndex += 1
        }
    }
}
```

##### Optimal

```swift
class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var lastNonZeroIndex: Int = 0
        for (i, num) in nums.enumerated() {
            if num != 0 {
                let tmp = nums[lastNonZeroIndex]
                nums[lastNonZeroIndex] = num
                nums[i] = tmp
                lastNonZeroIndex += 1
            }
        }
    }
}
```