The Zigzag String Conversion problem (LeetCode #6) asks us to rearrange a string such as "PAYPALISHIRING" into a two-dimensional zigzag wave across numRows horizontal rows, and then read the characters row-by-row from top to bottom. While the problem statement appears visual, designing an optimal C++ solution requires translating two-dimensional coordinate movement into deterministic one-dimensional index arithmetic that minimizes heap allocations and CPU branch mispredictions.

Problem Formulation & Geometric Index Mapping

Given an input string s of length N and an integer numRows (R), characters traverse straight down column 0 from row 0 to row R - 1, then step diagonally up and right from row R - 2 to row 1, before starting the next vertical column. For s = "PAYPALISHIRING" and numRows = 3, the geometric grid looks like this:

Row 0: P   A   H   N
Row 1: A P L S I I G
Row 2: Y   I   R

Concatenated Output: "PAHNAPLSIIGYIR"

For numRows = 4 on the same input, the diagonal climb spans two intermediate rows (r = 2 and r = 1) before reaching the top peak again:

Row 0: P     I     N
Row 1: A   L S   I G
Row 2: Y A   H R
Row 3: P     I

Concatenated Output: "PINALSIGYAHRPI"

Boundary Short-Circuits

Before allocating buffers or computing strides, two degenerate cases must be short-circuited in O(1) logic:

• Single Row (numRows <= 1): No vertical or diagonal oscillation is possible; every character resides on row 0, so the original string s is returned immediately.
• Row Count Exceeds String Length (numRows >= s.size()): Every character occupies its own row down the initial vertical column, meaning row-by-row concatenation is identical to s.

Approach 1: Directional Row-Buffer Simulation in C++

The most intuitive O(N) implementation models a cursor currRow that steps from 0 to numRows - 1 and flips its vertical direction vector (step = +1 vs. step = -1) whenever it hits the top boundary (r = 0) or bottom boundary (r = R - 1).

#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::string convert(const std::string& s, int numRows) {
        if (numRows <= 1 || static_cast<std::size_t>(numRows) >= s.size()) {
            return s;
        }

        std::vector<std::string> rows(numRows);
        const std::size_t estimatedRowCap = (s.size() / numRows) + 2;
        for (auto& row : rows) {
            row.reserve(estimatedRowCap);
        }

        int currRow = 0;
        int step = -1; // Flips immediately to +1 at index 0 (currRow == 0)

        for (char c : s) {
            rows[currRow].push_back(c);
            if (currRow == 0 || currRow == numRows - 1) {
                step = -step;
            }
            currRow += step;
        }

        std::string result;
        result.reserve(s.size());
        for (const auto& row : rows) {
            result.append(row);
        }
        return result;
    }
};

Approach 2: Direct Cycle-Stride Arithmetic (Zero Intermediate Buffers)

While the row-buffer simulation runs in O(N) time, it allocates a std::vector of R separate std::string heap buffers. We can eliminate all intermediate allocations by writing directly into a single pre-allocated output string of length N.

Observe that every complete V-shaped wave consists of R vertical characters followed by R - 2 diagonal characters, yielding a constant cycle period:

cycleLen = 2 * numRows - 2

• Outer Rows (r = 0 and r = numRows - 1): Contain exactly one character per cycle at index j + r, where j = k * cycleLen.
• Interior Rows (0 < r < numRows - 1): Contain two characters per cycle—the downward vertical character at j + r, and the upward diagonal character at j + cycleLen - r.

#include <string>

class StrideSolution {
public:
    std::string convert(const std::string& s, int numRows) {
        const int n = static_cast<int>(s.size());
        if (numRows <= 1 || numRows >= n) {
            return s;
        }

        std::string result;
        result.reserve(n);
        const int cycleLen = 2 * numRows - 2;

        for (int r = 0; r < numRows; ++r) {
            for (int j = 0; j + r < n; j += cycleLen) {
                // Primary vertical column character
                result.push_back(s[j + r]);

                // Secondary diagonal character for interior rows
                const int diagIdx = j + cycleLen - r;
                if (r != 0 && r != numRows - 1 && diagIdx < n) {
                    result.push_back(s[diagIdx]);
                }
            }
        }
        return result;
    }
};

Memory Layout, Cache Locality & Benchmark Comparison

In latency-sensitive C++20 workloads, the cycle-stride implementation outperforms vector-of-strings simulation for strings larger than the Small String Optimization (SSO) threshold (typically 15 or 22 bytes on 64-bit libstdc++/libc++):

• Time Complexity: Both algorithms visit each character a constant number of times, achieving strict O(N) runtime complexity.
• Auxiliary Space Complexity: Row simulation requires O(N) auxiliary heap space across R vector buckets before final concatenation, whereas cycle-stride arithmetic uses O(1) auxiliary working memory beyond the returned std::string buffer.