Problem Definition

Given a fixed-length array of integers, the objective is to duplicate every occurrence of the value zero. When a zero is duplicated, all subsequent elements must be shifted one position to the right. Any values that would extend beyond the original array boundaries are discarded. The transformation must be executed directly within the provided memory buffer without allocating additional space or returning a new collection.

Core Constraints

• The input buffer possesses a static size that cannot be dynamically resized.
• Each 0 encountered must be written twice, effectively displacing trailing data.
• Modifications are strictly in-place with a void return signature.

Naive Iterative Approach

A direct implementation scans the sequence from left to right. Upon detecting a zero, the algorithm shifts all elements to its right by one index to create space, inserts the duplicate zero, and advances the traversal index by two to skip the newly formed pair. This method relies on nested loops for shifting, resulting in a quadratic time complexity of O(N²).

class Solution {
public:
    void duplicateZeros(std::vector<int>& input) {
        int capacity = static_cast<int>(input.size());
        for (int scanIdx = 0; scanIdx < capacity; ++scanIdx) {
            if (input[scanIdx] == 0) {
                for (int shiftIdx = capacity - 1; shiftIdx > scanIdx + 1; --shiftIdx) {
                    input[shiftIdx] = input[shiftIdx - 1];
                }
                if (scanIdx + 1 < capacity) {
                    input[scanIdx + 1] = 0;
                }
                ++scanIdx; // Bypass the duplicated zero
            }
        }
    }
};

Optimized Two-Pointer Strategy

To eliminate redundant shifting operations, we can precalculate the final destination of each element before writing begins. This technique employs two sequential passes: the first determines write indices, and the second populates the array from right to left to prevent overwriting unread data.

Phase 1: Locate Terminal Write Position

Initialize a read pointer at the start and a write pointer just before the beginning. Traverse forward with the read pointer. For every non-zero value, advance the write pointer by one. For each zero, advance it by two. Terminate the forward traversal once the write pointer reaches or surpasses the final valid index of the buffer.

Phase 2: Boundary Adjustment

If the write pointer lands exactly on the array length after processing a zero, it indicates that the duplicate zero falls outside the allocated memory. In this case, place a single zero at the very end of the buffer, then decrement both pointers appropriately to align with the next element to process.

Phase 3: Reverse Population

Traverse backwards from the last valid read position down to zero. Copy the source value to the current write position. If the source is non-zero, decrement the write pointer once. If it is zero, write the value twice and decrement the write pointer by two. Continue until the read pointer moves past the start.

class Solution {
public:
    void duplicateZeros(std::vector<int>& buffer) {
        int limit = buffer.size();
        int readIdx = 0;
        int writeIdx = -1;

        // Pass 1: Calculate final destination indices
        while (readIdx < limit) {
            writeIdx += (buffer[readIdx] == 0) ? 2 : 1;
            if (writeIdx >= limit - 1) {
                break;
            }
            ++readIdx;
        }

        // Handle truncated zero at the boundary
        if (writeIdx == limit) {
            buffer[limit - 1] = 0;
            writeIdx -= 2;
            --readIdx;
        }

        // Pass 2: Fill backwards to preserve data integrity
        while (readIdx >= 0) {
            if (buffer[readIdx] != 0) {
                buffer[writeIdx] = buffer[readIdx];
                --writeIdx;
            } else {
                buffer[writeIdx--] = 0;
                buffer[writeIdx--] = 0;
            }
            --readIdx;
        }
    }
};

Performance Characteristics

The two-pass mehtodology visits each element at most twice, reducing the overall runtime to O(N). Since the algorithm operates exclusively within the original memory allocation and requires no temporary storage, the auxiliary space complexity remains strictly O(1).