Day #4/50 of Learning DSA

Embarking on the fourth day of my 50-day journey into mastering Data Structures and Algorithms (DSA), I found myself juggling college commitments and summer training evaluations. Despite the hectic schedule, I managed to tackle the "Move Zeroes" problem, exploring various approaches to optimize the solution. This experience not only reinforced my understanding of algorithmic strategies but also highlighted the importance of perseverance and time management in the learning process. Join me as I delve into the intricacies of this problem and share insights from today's learning adventure.

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.

BruteForce Approach:

• Use nested loops to repeatedly swap zeros with non-zero elements by comparing adjacent pairs and pushing non-zero values to the front, resulting in a time complexity of O(n²).

    void moveZeroes(vector<int>& nums) {
        if(nums.size()==1) return;

        for(int j=0; j<nums.size()-1; j++){
            int ptr1=0;
            int ptr2=1;
            for(int i=0; i<nums.size()-1; i++){
                if(nums[ptr2]!=0 && nums[ptr1]==0){
                    int temp = nums[ptr2];
                    nums[ptr2] = nums[ptr1];
                    nums[ptr1] = temp;
                }
                ptr1++;
                ptr2++;
            }
        }
    }

Optimal Approach:

• Create a tracker ptr1 to track next of non-zero elements.

• Create another tracker and traverse the array using ptr2.

• Move the non-zero element to the position at ptr1.

• Swap the elements if ptr1 and ptr2 are not equal and increment ptr1 to the next position.

    void moveZeroes(vector<int>& nums) {
        int ptr1 = 0;

        for (int ptr2 = 0; ptr2 < nums.size(); ptr2++) {
            if (nums[ptr2] != 0) {
                if (ptr1 != ptr2) {
                    nums[ptr1] = nums[ptr2];
                    nums[ptr2] = 0;
                }
                ptr1++;
            }
        }
    }