283. Move Zeroes

Problem Statement: Source

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

Solution:

Thought process:

1. Initially i=0 and j=0.
2. Take i to the first zero and do i=j.
3. Now move j to the first non-zero element and swap them.
4. move i++ and j++.

Another more efficient way is to think about quickSort algo involving a pivot and segregate type A and type B type of elements in array.

Pecoding soln

class Solution {
 
	public void swap(int i, int j, int[] nums) {
		int nonZero = nums[j];
		nums[j] = nums[i];
		nums[i] = nonZero;
	}
	
	public void moveZeroes(int[] nums) {
		int i = 0;
		int j = 0;
		
		// 0 to j - 1 => nonZero elements
		// j to i - 1 => Zeros
		// i to end => Unknown
		
		while (i < nums.length) {
			if(nums[i] == 0){
				i++;
			} else{
				swap(i, j, nums);
				i++; j++;
			}
		}
	}
 
}