LeetCode Solution: 283. Move Zeroes

Zeroes Got You Down? Let's Kick 'Em to the Curb! (LeetCode 283: Move Zeroes)

Hey there, future coding rockstars! 👋 Vansh2710 here, and today we're tackling a super common, yet incredibly insightful, LeetCode problem: 283. Move Zeroes. This problem is a fantastic introduction to a powerful technique and teaches us to think cleverly about modifying arrays.

Don't let the simplicity fool you; mastering this kind of problem builds a solid foundation for much tougher challenges. Ready to make those zeroes move? Let's dive in!

The Problem: Zeroes on the Loose!

Imagine you have a list of numbers, like [0, 1, 0, 3, 12]. Your mission, should you choose to accept it, is to rearrange this list so that all the zeroes are at the very end. But there are a couple of crucial rules:

1. Maintain Relative Order: The non-zero numbers must stay in their original order. So, 1 must still come before 3, and 3 before 12. You can't just sort the array!
   • [0, 1, 0, 3, 12] should become [1, 3, 12, 0, 0], not [0, 0, 1, 3, 12] or [1, 12, 3, 0, 0].
2. In-Place Modification: This is the big one! You can't create a new array and copy elements over. You have to modify the original array directly. This is like tidying up your room without using an extra box to put things into temporarily – you're just moving things around within the existing space.

Example 1:
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Example 2:
Input: nums = [0]
Output: [0]

Seems simple enough, right? But the "in-place" and "relative order" constraints make us think a little more deeply!

The "Aha!" Moment: Focus on What Matters!

When faced with a problem that asks us to move certain elements to the end while maintaining the order of others, a common pitfall is to try and move the "bad" elements (the zeroes) to their destination directly. You might think, "If I see a zero, swap it with the next element until it's at the end!" But this quickly gets messy and breaks the relative order of non-zeroes.

Instead, let's flip our perspective: what if we focus on the elements we want to keep in order – the non-zero numbers?

The "aha!" moment here is realizing that we can effectively "collect" all the non-zero elements at the beginning of the array, in their correct relative order. Once we've done that, all the remaining spots at the end of the array must be zeroes. This way, we ensure both the relative order and the in-place requirement.

Our Strategy: The Two-Pointer Dance!

This problem is a classic candidate for the two-pointer technique. We'll use two pointers:

1. nonZeroPointer: This pointer will keep track of where the next non-zero element should be placed. It essentially marks the boundary between the "non-zero section" and the "unknown/zero section" of our array. It starts at the beginning (index 0).
2. i (or currentPointer): This pointer will iterate through the entire array from left to right, checking each element.

Here's the step-by-step breakdown:

1. Initialize nonZeroPointer to 0. This is where our first non-zero number will go.
2. Iterate through the array with i (from 0 to nums.size() - 1).
3. For each nums[i]:
   • If nums[i] is NOT a zero: This is a number we want to keep at the beginning!
     • We put nums[i] at nums[nonZeroPointer].
     • Crucially, if i and nonZeroPointer are different, it means we just moved a non-zero number from a later position (i) to an earlier position (nonZeroPointer). The element that was originally at nums[i] (which was a zero that we overwrote, or a non-zero that we moved) is now at nums[nonZeroPointer]. To ensure the "fill with zeroes" part implicitly, we perform a swap. If i and nonZeroPointer are the same, it means nums[i] is already in its correct non-zero position, and we don't need to swap it with itself.
     • Increment nonZeroPointer by 1, because the spot it was pointing to is now filled with a non-zero value, and the next non-zero should go to the next available spot.
4. After the loop finishes, all non-zero elements will be at the beginning of the array, in their correct relative order. All elements from nonZeroPointer to the end of the array will implicitly be zeroes (due to the swaps moving zeroes out of the way or overwriting them with zeroes when i == nonZeroPointer).

Let's trace [0, 1, 0, 3, 12]:

i	nums[i]	nonZeroPointer	nums (before swap)	Condition (nums[i] != 0)	Action	nums (after swap)
0	0	0	[0, 1, 0, 3, 12]	False	None	[0, 1, 0, 3, 12]
1	1	0	[0, 1, 0, 3, 12]	True	swap(nums[1], nums[0]); nonZeroPointer becomes 1	[1, 0, 0, 3, 12]
2	0	1	[1, 0, 0, 3, 12]	False	None	[1, 0, 0, 3, 12]
3	3	1	[1, 0, 0, 3, 12]	True	swap(nums[3], nums[1]); nonZeroPointer becomes 2	[1, 3, 0, 0, 12]
4	12	2	[1, 3, 0, 0, 12]	True	swap(nums[4], nums[2]); nonZeroPointer becomes 3	[1, 3, 12, 0, 0]

Loop ends. The array is [1, 3, 12, 0, 0]. Perfect!

The Code

#include <vector> // Required for std::vector
#include <algorithm> // Required for std::swap

class Solution {
public:
    void moveZeroes(std::vector<int>& nums) {
        int nonZeroPointer = 0; // Pointer for the next position for a non-zero element

        // Iterate through the array with 'i'
        for (int i = 0; i < nums.size(); ++i) {
            // If the current element is non-zero,
            // it means we found an element that belongs in the non-zero section
            if (nums[i] != 0) {
                // If 'i' and 'nonZeroPointer' are different, it means
                // nums[i] is a non-zero element and nonZeroPointer is pointing
                // to a zero (or an element that will be a zero after the swap).
                // We swap to move the non-zero element to its correct position.
                // If i == nonZeroPointer, the element is already in place,
                // so we don't need to swap it with itself.
                if (i != nonZeroPointer) {
                    std::swap(nums[i], nums[nonZeroPointer]);
                }
                // Move the nonZeroPointer forward, indicating the next spot
                // for another non-zero element.
                nonZeroPointer++;
            }
        }
    }
};

Complexity Analysis

Let's break down how efficient our solution is:

• Time Complexity: O(N)
  • We iterate through the array exactly once with our i pointer.
  • Inside the loop, operations like if checks, !=, and swap take constant time, O(1).
  • Therefore, the total time complexity is directly proportional to the number of elements in the array, N.
• Space Complexity: O(1)
  • We are modifying the array directly "in-place" without creating any auxiliary data structures that scale with the input size.
  • The nonZeroPointer and i variables only take up a constant amount of extra space.

This solution is highly optimized, satisfying the "minimize total number of operations" follow-up as it performs at most N swaps and N comparisons.

Key Takeaways

1. Two-Pointer Power: The two-pointer technique is your best friend for array manipulation problems, especially those involving sorting, partitioning, or relative ordering.
2. In-Place Challenges: When a problem demands "in-place" modification, think about how you can reuse the existing memory. Often, this involves overwriting elements or clever swapping.
3. Flip the Perspective: Sometimes, focusing on what you don't want can be harder than focusing on what you do want. Instead of chasing zeroes, we collected non-zeroes.
4. Practice Makes Perfect: This problem might seem straightforward now, but the "aha!" moment comes with practice. Keep solving, keep thinking, and soon these patterns will be second nature!

Happy coding, and may your arrays always be perfectly ordered!

---

Author Account: Vansh2710
Time Published: 2026-04-26 23:36:47