# Move Zeroes
**Difficulty:** EASY
[External](https://leetcode.com/problems/move-zeroes)
Canonical: https://scaleengineer.com/dsa/problems/move-zeroes
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [Nvidia](https://scaleengineer.com/companies/nvidia), [Ozon](https://scaleengineer.com/companies/ozon), [SAP](https://scaleengineer.com/companies/sap), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [josh technology](https://scaleengineer.com/companies/josh-technology), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [CEDCOSS](https://scaleengineer.com/companies/cedcoss), [Anduril](https://scaleengineer.com/companies/anduril), [VK](https://scaleengineer.com/companies/vk), [NetApp](https://scaleengineer.com/companies/netapp), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [DevRev](https://scaleengineer.com/companies/devrev)
---
## 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 <= 104`
* `-231 <= nums[i] <= 231 - 1`

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

# Approaches
## Brute Force with Extra Array
Use an additional array to store non-zero elements first, then fill remaining positions with zeros.
**Time:** O(n) where n is the length of the array - requires two passes through the array · **Space:** O(n) where n is the length of the array - requires extra array of same size
**Pros:** Simple to understand and implement; Maintains relative order of non-zero elements; Only requires two passes through the array
**Cons:** Uses extra space; Not in-place as required by the problem; Requires copying elements back to original array
### Explanation
This approach uses an extra array to solve the problem in two passes:

1. Create a new array of the same size as input
2. Iterate through the input array and copy non-zero elements to the new array
3. Fill remaining positions with zeros
4. Copy back elements to original array

```java
public void moveZeroes(int[] nums) {
    int[] result = new int[nums.length];
    int nonZeroIndex = 0;
    
    // First pass: copy non-zero elements
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            result[nonZeroIndex++] = nums[i];
        }
    }
    
    // Fill remaining positions with zeros
    while (nonZeroIndex < nums.length) {
        result[nonZeroIndex++] = 0;
    }
    
    // Copy back to original array
    for (int i = 0; i < nums.length; i++) {
        nums[i] = result[i];
    }
}
```
### Algorithm
1. Create new array of same size as input
2. Copy non-zero elements maintaining order
3. Fill remaining positions with zeros
4. Copy back to original array

## Two Pointers Approach
Use two pointers to track the position for next non-zero element and current element, swapping when necessary.
**Time:** O(n) where n is the length of the array - single pass through the array · **Space:** O(1) - only uses two pointers regardless of input size
**Pros:** In-place solution - no extra space needed; Single pass through the array; Maintains relative order of non-zero elements; Minimal number of operations
**Cons:** Performs unnecessary swaps when elements are already in correct position
### Explanation
This approach uses two pointers to solve the problem in a single pass:

1. Initialize two pointers: lastNonZeroFoundAt and cur
2. As we iterate cur pointer, whenever we find a non-zero element, we swap it with the element at lastNonZeroFoundAt
3. Increment lastNonZeroFoundAt after each swap

```java
public void moveZeroes(int[] nums) {
    int lastNonZeroFoundAt = 0;
    
    // Move all non-zero elements to front
    for (int cur = 0; cur < nums.length; cur++) {
        if (nums[cur] != 0) {
            int temp = nums[lastNonZeroFoundAt];
            nums[lastNonZeroFoundAt] = nums[cur];
            nums[cur] = temp;
            lastNonZeroFoundAt++;
        }
    }
}
```
### Algorithm
1. Initialize lastNonZeroFoundAt = 0
2. Iterate through array with cur pointer
3. When non-zero element found, swap with lastNonZeroFoundAt position
4. Increment lastNonZeroFoundAt

## Optimized Two Pointers
Use two pointers but optimize by avoiding unnecessary swaps when elements are already in correct position.
**Time:** O(n) where n is the length of the array - single pass through the array · **Space:** O(1) - only uses two pointers regardless of input size
**Pros:** In-place solution - no extra space needed; Single pass through the array; Maintains relative order of non-zero elements; Minimizes number of operations by avoiding unnecessary swaps; Most efficient solution possible for this problem
**Cons:** Slightly more complex logic than basic two pointers approach
### Explanation
This approach optimizes the two pointers solution by only moving elements when necessary:

1. Use two pointers: nonZeroPos and cur
2. nonZeroPos tracks where next non-zero element should go
3. Only move elements when they are out of position
4. Fill remaining positions with zeros

```java
public void moveZeroes(int[] nums) {
    int nonZeroPos = 0;
    
    // Move all non-zero elements to front
    for (int cur = 0; cur < nums.length; cur++) {
        if (nums[cur] != 0) {
            if (cur != nonZeroPos) {
                nums[nonZeroPos] = nums[cur];
                nums[cur] = 0;
            }
            nonZeroPos++;
        }
    }
}
```
### Algorithm
1. Initialize nonZeroPos = 0
2. Iterate through array
3. When non-zero element found, move it to nonZeroPos if needed
4. Increment nonZeroPos

# Solutions
### Java

```java
class Solution { public void moveZeroes ( int [] nums ) { int i = - 1 , n = nums . length ; for ( int j = 0 ; j < n ; ++ j ) { if ( nums [ j ] != 0 ) { int t = nums [++ i ]; nums [ i ] = nums [ j ]; nums [ j ] = t ; } } } }
```

### JavaScript

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

```

### CPP

```cpp
class Solution {
public:
  void moveZeroes(vector<int> &nums) {
    int i = -1, n = nums.size();
    for (int j = 0; j < n; ++j) {
      if (nums[j]) {
        swap(nums[++i], nums[j]);
      }
    }
  }
};

```

### Python

```python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None: i = - 1 for j, x in enumerate(nums): if x: i += 1 nums[i], nums[j] = nums[j], nums[i]

```