Problem: Move Zeros to the End

Given an integer array nums, move all 0s to the end of it while maintaining the relative order of the non-zero elements.

You need to 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]

Explanation: The non-zero elements are [1, 3, 12] and the zeros are moved to the end, while maintaining the relative order of the non-zero elements.

Example 2:

Input:

nums = [0]

Output:

[0]

Constraints:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

Follow-up:

Can you minimize the total number of operations done?

Approach and C Code Explanation:

To solve this problem efficiently in-place, we can use a two-pointer approach:

• Left pointer (left): Keeps track of the position where the next non-zero element should be placed.
• Right pointer (right): Iterates through the array to find non-zero elements.

For each non-zero element found by the right pointer, we swap it with the element at the left pointer, then increment the left pointer. This ensures that all non-zero elements are moved to the front, and zeros are pushed to the end.

C Code:

#include <stdio.h>

// Function to move all zeros to the end
void moveZeroes(int* nums, int numsSize) {
    int left = 0;

    for (int right = 0; right < numsSize; right++) {
        // If current element is non-zero, swap it with the element at 'left'
        if (nums[right] != 0) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++; // Increment the left pointer
        }
    }
}

// Function to print the array
void printArray(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("n");
}

int main() {
    int nums[] = {0, 1, 0, 3, 12};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    printf("Original array:n");
    printArray(nums, numsSize);
    
    // Move zeros to the end
    moveZeroes(nums, numsSize);
    
    printf("Array after moving zeros:n");
    printArray(nums, numsSize);
    
    return 0;
}

Explanation of the Code:

• moveZeroes function:
  • It uses two pointers: left (for the position of the next non-zero element) and right (to iterate through the array).
  • When a non-zero element is found at nums[right], it is swapped with the element at nums[left]. After the swap, left is incremented to track the next available spot for a non-zero element.
• printArray function: Prints the array after the zeros have been moved to the end.
• Time complexity: The solution runs in O(n), where n is the number of elements in the array because each element is processed once.
• Space complexity: The solution is O(1) since it only uses a constant amount of extra space (just the pointers).

Example Output:

Input:

Original array:
0 1 0 3 12 
Array after moving zeros:
1 3 12 0 0