LeetCode #283 Move Zeroes Solution & Explanation

Klook.com
Post Views: 167

LeetCode 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.

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

Solution

In the problem description, it states that we need to perform the operation in-place.

So, we are not allowed to generate an array or a list to store the non-zero values.

C# Solution

Solution1

public class Solution {
    public void MoveZeroes(int[] nums) {
        int Idx = 0;
        for(int i=0; i<nums.Length; i++){
            if (nums[i] != 0)
            {
                var tmp = nums[Idx];
                nums[Idx] = nums[i];
                nums[i] = tmp;
                Idx++;
            }
        }
    }
}

Time Complexity : O(n)

Idx represents the current position where a swap operation should occur. While iterating through the array, when encountering a non-zero element, we swap it with the position indicated by Idx. Then, we move Idx one position forward. However, when encountering a zero element, we refrain from performing a swap operation, and instead, we keep Idx unchanged. This ensures that the next non-zero element encountered will be placed correctly behind the current zero element.

In essence, Idx serves as the marker for swap operations. When a zero element is encountered, Idx indicates the position of the current zero element, ensuring correct placement of subsequent non-zero elements.

⚠️And here’s my first try

public class Solution {
    public void MoveZeroes(int[] nums) {
        int cnt = 0;
        int max = nums.Length;
        
        if(max!=1)
        {
            for(int i = 0; i<max;i++)
            {

                int now = nums[i];
                if(i == max-cnt)
                {
                    break;
                }
                
                if(now == 0)
                {
                    cnt+=1;
                    for(int j=i;j<max-1;j++)
                    {
                        nums[j] = nums[j+1];
                    }
                    nums[max-1] = 0;
                    if(nums[i] == 0)
                    {
                        i-=1;   
                    }
                }

            } 
        }
    }
}

Time Complexity : O(n2)

This solution doesn’t use extra space and employs two pointers, i and j, to traverse the array. However, it has a time complexity of O(n2), which can significantly impact performance, especially for larger arrays.

Java Solution

Solution1

class Solution {
    public void moveZeroes(int[] nums) {
        int Idx = 0;
        for(int i=0; i<nums.length; i++){
            if (nums[i] != 0)
            {
                int tmp = nums[Idx];
                nums[Idx] = nums[i];
                nums[i] = tmp;
                Idx++;
            }
        }
    }
}

Python3 Solution

Solution1

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        Idx = 0
        for i in range(len(nums)):
            if (nums[i] != 0):
                tmp = nums[Idx]
                nums[Idx] = nums[i]
                nums[i] = tmp
                Idx+=1

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link: Move Zeroes – LeetCode

Some Random LeetCode posts

Tags

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *