King Of Interviews

Move Zeroes: 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 <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

Try this Problem on your own or check similar problems:

Solution:

public void moveZeroes(int[] nums) {
  int writer = 0;
  for(int i = 0; i < nums.length; ++i){
      if(nums[i] != 0){
          nums[writer++] = nums[i];
      }
  }
  while(writer < nums.length) nums[writer++] = 0;
}

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Explanation:

We traverse the whole input array leading to linear time complexity, and since we have to make the change in-place, without copying or creating new instance we have constant space complexity. Problems like this can be solved using two pointers/iterators, writer which actually is doing the changes to the array and iter in this case i in the for loop which is only going through array and reading values. Since we’re only interested in non-zero value we only write those, incrementing writer every time we encounter non-zero value. We fill the rest of array with zeroes (all other non-zero values have been already written).

Move Zeroes