Leetcode 283. Move Zeroes

Problem

Given an array of integers, the task is to move all 0's to the end of the array while maintaining the relative order of the non-zero elements.

This operation should be done in-place i.e. without making a copy of the array and the goal is to minimize the total number of operations.

For example,

1
2plaintext
3Input: [0,1,0,3,12]
4Output: [1,3,12,0,0]

Here, we can see that all the zeroes are moved to the end while the non-zero integers (1, 3, 12) are in same order as they were in the input array.

Approach of the Solution

A simple approach would be to maintain a counter i for the current index where the next non-zero number should be placed. We iterate through all the elements of the array, and if the current element is non-zero, we place it at the index i and increment i. If the current element is zero, we simply continue with our iteration. At the end of this iteration, all our non-zero numbers would be at the beginning of the array in their relative order, and i would be pointing to the first zero in the array. Now, we simply iterate i to the end of the array and for each index, we place a zero.

Solutions

1. Python

1
2python
3class Solution:
4    def moveZeroes(self, nums):
5        i = 0
6        for num in nums:
7            if num != 0:
8                nums[i] = num
9                i += 1
10
11        while i < len(nums):
12            nums[i] = 0
13            i += 1
14        return nums

2. Java

1
2java
3public class Solution {
4    public void moveZeroes(int[] nums) {
5        int i = 0;
6        for (int num: nums) {
7            if(num != 0){
8                nums[i] = num;
9                i++;
10            }
11        }
12        
13        while(i < nums.length){
14            nums[i] = 0;
15            i++;
16        }
17    }
18}

3. Javascript

1
2javascript
3var Solution = {
4    moveZeroes: function(nums) {
5        let i = 0;
6        for(let num of nums){
7            if(num !== 0){
8                nums[i] = num;
9                i++;
10            }
11        }
12        
13        while(i < nums.length){
14            nums[i] = 0;
15            i++;
16        }
17        return nums;
18    }
19}

4. C++

1
2cpp
3class Solution {
4public:
5    void moveZeroes(vector<int>& nums) {
6        int i = 0;
7        for (const int num : nums)
8            if (num != 0)
9                nums[i++] = num;
10
11        while (i < nums.size())
12            nums[i++] = 0;
13    }
14};

5. C#

1
2csharp
3public class Solution {
4    public void MoveZeroes(int[] nums) {
5        int i = 0;
6        foreach(int num in nums){
7            if(num != 0){
8                nums[i] = num;
9                i++;
10            }
11        }
12        
13        while(i < nums.Length){
14            nums[i] = 0;
15            i++;
16        }
17    }
18}

The solutions provided are efficient and in place, as they only iterate through the array once, and do not require any extra space. They can be run on any major programming platform supporting the corresponding languages.

They follow the same logic in all the languages - initializing counter 'i' from the start of the array and incrementing it whenever a non-zero value is encountered and replacing the value at the current position with this non-zero value. Once all the non-zero values are shifted to the front of the array, we simply fill the remaining part of the array with 0s till the end.

Although the approach is pretty straight-forward, there are subtle details to take care of, for instance, dealing with an empty array. The solutions take care of that as well. Also, since array indexing in different languages start from different numbers and the array length or size is calculated differently, those small changes need to be taken care of in these languages. But the overall concept remains the same in all these languages.

If you have a keen eye, you’ll spot that the code snippets for each of the languages look remarkably similar to each other. The syntax for loops and conditionals is undoubtedly different, but the same problem-solving logic applies across all implementations.

That's the beauty of algorithm problem-solving - once you have the underlying logic, implementation in any language is simply a matter of knowing the language's syntax.

So, one can definitely conclude that this problem can be solved in constant space complexity (since no extra space other than input array is used) and linear time complexity (since array is traversed only once). It's an optimal solution for this problem scenario.

Hence Run, Debug test on major languages like java, python, C++, javascript, C# have been covered in this article and can be tested with multiple test cases.