class Solution {
    /**
     * T(N) = O(2N)
     * Create a temp arraylist to store non-zeros elements
     * Run a loop over tempArray list and start storing non-zero element back to original array from index=0
     * At last we will run loop again until index < array.length, because we have to store zeroes at last of array
     */
    public void moveZeroes(int[] nums) {
        ArrayList<Integer> tempList = new ArrayList<>();
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i] != 0)
            {
                tempList.add(nums[i]);
            }
        }

        int zeroes = nums.length - tempList.size();
        int index = 0;
        for(int i=0;i<tempList.size();i++)
        {
            nums[index] = tempList.get(i);
            index++;
        }

        while(index < nums.length)
        {
            nums[index] = 0;
            index++;
        }
    }
    
    /**
     * T(N) = O(N)
     * First find the index of zero element that appears at very first in the array, say stored it in "index"
     * Run a loop over array from starting index as i=index+1 and run loop until array.length
     * during traversal check if element is non-zero element, if yes then swap arr[index] with arr[i]
     * and after swapping increment index++ 
    */
    public void moveZeroes(int[] nums) {
        int index = 0;
        for(int i=0; i<nums.length; i++)
        {
            if(nums[i] == 0)
            {
                index = i;
                break;
            }
        }

        // when there are no zeroes in an array
        if(index == -1)
            return;

        for(int i=index+1; i<nums.length; i++)
        {
            if(nums[i] != 0)
            {
                // swap with 0
                int temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
                index++;
            }
        }
    }
}