algoadvance

Leetcode 283. Move Zeroes

Problem Statement

The problem is to move all zeros in a given integer array nums to the end of the array while maintaining the relative order of the non-zero elements. The operation should be performed in-place.

Example:

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

Clarifying Questions

1. Q: Can the array contain negative numbers? A: Yes, the array can contain negative numbers.

2. Q: Are there any constraints on the array length? A: The array length can vary, but typically within the constraints of an integer array in memory.

3. Q: Do we need to return anything or modify the array in place? A: The array should be modified in place, and there’s no need to return anything.

Strategy

1. Two Pointers Approach:
   • Use two pointers:
     • One lastNonZeroFoundAt to keep track of the position of the last non-zero found.
     • One cur to traverse the array.
   • Traverse the array with cur. Whenever a non-zero element is found, swap it with the element at the lastNonZeroFoundAt index and increment lastNonZeroFoundAt.
   • Continue this process until the end of the array is reached.
   • This approach guarantees that all non-zero elements are moved to the beginning part of the array, and the remaining part of the array will be filled with zeros.

Code

#include <vector>

void moveZeroes(std::vector<int>& nums) {
    int lastNonZeroFoundAt = 0; // Pointer to keep track of last non-zero element found
    
    // Move all non-zero elements forward
    for (int cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            std::swap(nums[lastNonZeroFoundAt], nums[cur]);
            lastNonZeroFoundAt++;
        }
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once with the cur pointer and occasionally perform swaps.
• Space Complexity: O(1), since we are modifying the array in-place and no extra space is used.

Explanation

• Initialize the lastNonZeroFoundAt pointer to 0.
• Iterate over the array using the cur pointer.
• When a non-zero element is encountered (nums[cur] != 0), swap it with the element at index lastNonZeroFoundAt and increment lastNonZeroFoundAt.
• By the end of the loop, all the non-zero elements would have been moved to the front of the array in their original order, and all the zero elements would be at the end of the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?