Move Zeroes

Problem Statement

The task is to rearrange elements within an integer array nums such that all zeros (0s) are moved to the end of the array, while ensuring that the order of the non-zero elements remains unchanged. This operation must be performed directly on the input array, meaning modifications should be done in-place without the aid of creating a duplicate array for processing. This problem tests one's capability to manipulate array indices and understand in-place algorithmic operations efficiently.

Examples

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 <= 104
• -231 <= nums[i] <= 231 - 1

Approach and Intuition

The main goal is to keep track of where the next non-zero element should be placed in the array. We can achieve this by employing a two-pointer technique:

1. One pointer, let's call it nonZeroIndex, will track the position where the next non-zero element should be placed.
2. Another pointer will iterate through the array, checking each element.

Breakdown of Algorithm:

1. Initialize nonZeroIndex to zero. This pointer marks the spot where the next non-zero number should be placed in the array.
2. Iterate over the array with another pointer called i.
   • If the element at i (nums[i]) is non-zero:
     • Move nums[i] to the position indicated by nonZeroIndex.
     • Increment nonZeroIndex.
   • If the element at i is zero, do nothing.
3. After processing all elements with the loop, all non-zero elements are now at the beginning, in their original relative order. The remainder of the array from nonZeroIndex to the end should be filled with zeros.

Visual Example:

Consider nums = [0,1,0,3,12]:

• Start with nonZeroIndex = 0.
• i = 0 → nums[0] is 0, do nothing.
• i = 1 → nums[1] is 1. Place 1 at nums[0] and increment nonZeroIndex to 1.
• i = 2 → nums[2] is 0, do nothing.
• i = 3 → nums[3] is 3. Place 3 at nums[1] and increment nonZeroIndex to 2.
• i = 4 → nums[4] is 12. Place 12 at nums[2] and increment nonZeroIndex to 3.
• Fill remaining places with 0s (from nums[3] onwards).

Result reflects as [1, 3, 12, 0, 0], matching our expected output with zeros at the end and non-zero elements maintaining their original sequence.

This method ensures in-place rearrangement with minimal space complexity and avoids unnecessary operations.

Solutions

class Solution {
public:
  void shiftZeroes(vector<int>& elements) {
      for (int lastNonZeroPos = 0, currIndex = 0; currIndex < elements.size(); currIndex++) {
          if (elements[currIndex] != 0) {
              swap(elements[lastNonZeroPos++], elements[currIndex]);
          }
      }
  }
};