[LeetCode] #283

In this article, we are going to look at how to solve the LeetCode Question 283, Move Zeroes.

Problem Statement

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]

Approach

Looking at the examples given by LeetCode, we can see that this is a problem we can solve using two pointers. Initially we need to create two pointers, left and right at 0 and 1 indexes respectively. Then we move the right pointer to check for non-zero elements. And when we found a non-zero element, we need to swap it with the left pointer and then move both the pointers by one.

But this is only true when the initial left pointer element’s value is 0. If the value is a non-zero, then we might be swapping non-zero values. To ensure that is not happening, we are moving the left pointer by 1, whenever the value of it is a non-zero value.

And also, we can just return the array if the length of the array is less than 2.

Solution

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        if(n < 2) return;

        int left = 0, right = 1;
        while(right < n){
            if(nums[left] != 0){
                left++;
                right++;
            } else if(nums[right] == 0){
                right++;
            } else {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
            }
        }
    }
}

Since we are not using any additional spaces in memory for this solution, the space complexity of this algorithm is O(1).

The time complexity of this algorithm is, O(n) because of the condition if(right < n) . Because that implies that the right pointer is accessing all the elements in the array.