This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an array `nums`

, write a function to move all `0`

's to the end of it while maintaining the relative order of the non-zero elements.

For example, given `nums = [0, 1, 0, 3, 12]`

, after calling your function, `nums`

should be `[1, 3, 12, 0, 0]`

.

**Note**:

- You must do this
**in-place**without making a copy of the array. - Minimize the total number of operations.

**Credits:**

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

b'

\n## Solution

\n

\n#### Approach #1 (Space Sub-Optimal) [Accepted]

\n\n

\n#### Approach #2 (Space Optimal, Operation Sub-Optimal) [Accepted]

\n\n

\n#### Approach #3 (Optimal) [Accepted]

\n\n

'
\n\n

\n\n

This question comes under a broad category of "Array Transformation". This category is the meat of tech interviews. Mostly because arrays are such a simple and easy to use data structure. Traversal or representation doesn\'t require any boilerplate code and most of your code will look like the Pseudocode itself.

\nThe 2 requirements of the question are:

\n- \n
- \n
Move all the 0\'s to the end of array.

\n \n - \n
All the non-zero elements must retain their original order.

\n \n

It\'s good to realize here that both the requirements are mutually exclusive, i.e., you can solve the individual sub-problems and then combine them for the final solution.

\n**C++**

void moveZeroes(vector<int>& nums) {\n int n = nums.size();\n\n // Count the zeroes\n int numZeroes = 0;\n for (int i = 0; i < n; i++) {\n numZeroes += (nums[i] == 0);\n }\n\n // Make all the non-zero elements retain their original order.\n vector<int> ans;\n for (int i = 0; i < n; i++) {\n if (nums[i] != 0) {\n ans.push_back(nums[i]);\n }\n }\n\n // Move all zeroes to the end\n while (numZeroes--) {\n ans.push_back(0);\n }\n\n // Combine the result\n for (int i = 0; i < n; i++) {\n nums[i] = ans[i];\n }\n}\n

**Complexity Analysis**

Space Complexity : . Since we are creating the "ans" array to store results.

\nTime Complexity: . However, the total number of operations are sub-optimal. We can achieve the same result in less number of operations.

\nIf asked in an interview, the above solution would be a good start. You can explain the interviewer(not code) the above and build your base for the next Optimal Solution.

\n\n

This approach works the same way as above, i.e. , first fulfills one requirement and then another. The catch? It does it in a clever way. The above problem can also be stated in alternate way, " Bring all the non 0 elements to the front of array keeping their relative order same".

\nThis is a 2 pointer approach. The fast pointer which is denoted by variable "cur" does the job of processing new elements. If the newly found element is not a 0, we record it just after the last found non-0 element. The position of last found non-0 element is denoted by the slow pointer "lastNonZeroFoundAt" variable. As we keep finding new non-0 elements, we just overwrite them at the "lastNonZeroFoundAt + 1" \'th index. This overwrite will not result in any loss of data because we already processed what was there(if it were non-0,it already is now written at it\'s corresponding index,or if it were 0 it will be handled later in time).

\nAfter the "cur" index reaches the end of array, we now know that all the non-0 elements have been moved to beginning of array in their original order. Now comes the time to fulfil other requirement, "Move all 0\'s to the end". We now simply need to fill all the indexes after the "lastNonZeroFoundAt" index with 0.

\n**C++**

void moveZeroes(vector<int>& nums) {\n int lastNonZeroFoundAt = 0;\n // If the current element is not 0, then we need to\n // append it just in front of last non 0 element we found. \n for (int i = 0; i < nums.size(); i++) {\n if (nums[i] != 0) {\n nums[lastNonZeroFoundAt++] = nums[i];\n }\n }\n // After we have finished processing new elements,\n // all the non-zero elements are already at beginning of array.\n // We just need to fill remaining array with 0\'s.\n for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {\n nums[i] = 0;\n }\n}\n

**Complexity Analysis**

Space Complexity : . Only constant space is used.

\nTime Complexity: . However, the total number of operations are still sub-optimal. The total operations (array writes) that code does is (Total number of elements).

\n\n

The total number of operations of the previous approach is sub-optimal. For example, the array which has all (except last) leading zeroes: [0, 0, 0, ..., 0, 1].How many write operations to the array? For the previous approach, it writes 0\'s times, which is not necessary. We could have instead written just once. How?\n..... \nBy only fixing the non-0 element,i.e., 1.

\nThe optimal approach is again a subtle extension of above solution. A simple realization is if the current element is non-0, its\' correct position can at best be it\'s current position or a position earlier. If it\'s the latter one, the current position will be eventually occupied by a non-0 ,or a 0, which lies at a index greater than \'cur\' index. We fill the current position by 0 right away,so that unlike the previous solution, we don\'t need to come back here in next iteration.

\nIn other words, the code will maintain the following invariant:

\n\n\n\n

\n- \n
\nAll elements before the slow pointer (lastNonZeroFoundAt) are non-zeroes.

\n- \n
\nAll elements between the current and slow pointer are zeroes.

\n

Therefore, when we encounter a non-zero element, we need to swap elements pointed by current and slow pointer, then advance both pointers. If it\'s zero element, we just advance current pointer.

\nWith this invariant in-place, it\'s easy to see that the algorithm will work.

\n**C++**

void moveZeroes(vector<int>& nums) {\n for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {\n if (nums[cur] != 0) {\n swap(nums[lastNonZeroFoundAt++], nums[cur]);\n }\n }\n}\n

**Complexity Analysis**

Space Complexity : . Only constant space is used.

\nTime Complexity: . However, the total number of operations are optimal. The total operations (array writes) that code does is Number of non-0 elements.This gives us a much better best-case (when most of the elements are 0) complexity than last solution. However, the worst-case (when all elements are non-0) complexity for both the algorithms is same.

\nAnalysis written by: @spandan.pathak

\n