ZigZag Conversion: Multiple Solutions and Complexity Analysis

Introduction to ZigZag Conversion

The ZigZag Conversion problem is a classic algorithmic challenge that appears frequently in coding interviews and competitive programming. Given a string and a number of rows, the task is to write the characters of the string in a zigzag pattern across those rows, then read the result row by row to produce the converted string.

While the problem itself may seem like a brainteaser, it teaches fundamental concepts about pattern recognition, index arithmetic, and simulation techniques. Mastering it sharpens your ability to translate visual patterns into efficient code — a skill that transfers directly to real-world problems involving matrix traversal, data reshaping, and stream processing.

What Is the ZigZag Pattern?

Imagine writing a string diagonally down and then up across a fixed number of rows, repeating until every character is placed. For example, with the input string "PAYPALISHIRING" and numRows = 3, the characters are arranged like this:

P   A   H   N
A P L S I I G
Y   I   R

Reading row by row produces the output: "PAHNAPLSIIGYIR". With numRows = 4, the same string becomes:

P     I    N
A   L S  I G
Y A   H R
P     I

The output is "PINALSIGYAHRPI". The key insight is that characters flow downward until they hit the bottom row, then flow upward until they hit the top row, and this cycle repeats.

Why It Matters

Beyond interview preparation, the ZigZag Conversion problem illustrates several important software engineering principles:

• Simulation vs. mathematical derivation: You can either simulate the process step by step or compute character positions directly with arithmetic. Both approaches are valuable in different contexts.
• Space-time tradeoffs: Some solutions use extra memory to simplify logic, while others compute indices on the fly to save space.
• Pattern generalization: The cycle length and index formulas generalize to many problems involving periodic patterns in arrays and strings.
• Edge case handling: Cases like numRows = 1 or strings shorter than the number of rows force you to think carefully about boundary conditions.

How to Use It: Multiple Solutions

Solution 1: Simulation with Row Buffers

The most intuitive approach is to simulate the zigzag writing process. Maintain a list of string builders, one per row, and a pointer that moves up and down as you iterate through the input. Append each character to the appropriate row, then concatenate all rows at the end.

function convertSimulation(s, numRows) {
    if (numRows === 1 || s.length <= numRows) {
        return s;
    }

    const rows = new Array(numRows).fill("");
    let currentRow = 0;
    let goingDown = false;

    for (const char of s) {
        rows[currentRow] += char;

        // Reverse direction at the top or bottom row
        if (currentRow === 0 || currentRow === numRows - 1) {
            goingDown = !goingDown;
        }

        currentRow += goingDown ? 1 : -1;
    }

    return rows.join("");
}

// Example usage
console.log(convertSimulation("PAYPALISHIRING", 3)); // "PAHNAPLSIIGYIR"
console.log(convertSimulation("PAYPALISHIRING", 4)); // "PINALSIGYAHRPI"
console.log(convertSimulation("A", 1));              // "A"

This solution is easy to understand and implement. The direction flag goingDown toggles whenever the pointer reaches either boundary, naturally producing the zigzag motion.

Solution 2: Visit by Row with Index Arithmetic

Instead of simulating the process, you can compute exactly which characters belong to each row. For a given numRows, the zigzag pattern has a cycle length of cycleLen = 2 * numRows - 2. Within each cycle, row i contains the character at position i and, if it is not the first or last row, an additional character at position cycleLen - i.

function convertByRow(s, numRows) {
    if (numRows === 1 || s.length <= numRows) {
        return s;
    }

    const n = s.length;
    const cycleLen = 2 * numRows - 2;
    let result = "";

    for (let row = 0; row < numRows; row++) {
        for (let j = 0; j + row < n; j += cycleLen) {
            // First character in the cycle for this row
            result += s[j + row];

            // Middle rows have a second character per cycle
            const secondIndex = j + cycleLen - row;
            if (row !== 0 && row !== numRows - 1 && secondIndex < n) {
                result += s[secondIndex];
            }
        }
    }

    return result;
}

// Example usage
console.log(convertByRow("PAYPALISHIRING", 3)); // "PAHNAPLSIIGYIR"
console.log(convertByRow("PAYPALISHIRING", 4)); // "PINALSIGYAHRPI"

This approach avoids the overhead of maintaining multiple buffers and a direction flag. It directly computes the indices, making it both elegant and efficient. The outer loop iterates over rows, and the inner loop jumps by cycleLen to visit each cycle.

Solution 3: Python Implementation with List of Characters

For Python developers, using a list of character lists and joining at the end is more efficient than repeated string concatenation, since strings in Python are immutable.

def convert(s: str, numRows: int) -> str:
    if numRows == 1 or len(s) <= numRows:
        return s

    rows = [[] for _ in range(numRows)]
    current_row = 0
    going_down = False

    for char in s:
        rows[current_row].append(char)
        if current_row == 0 or current_row == numRows - 1:
            going_down = not going_down
        current_row += 1 if going_down else -1

    return "".join("".join(row) for row in rows)

# Example usage
print(convert("PAYPALISHIRING", 3))  # PAHNAPLSIIGYIR
print(convert("PAYPALISHIRING", 4))  # PINALSIGYAHRPI
print(convert("A", 1))               # A

Solution 4: Java Implementation with StringBuilder

In Java, StringBuilder is the idiomatic choice for building strings incrementally. The simulation approach translates cleanly:

public class ZigZagConversion {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }

        int currentRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows[currentRow].append(c);
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        ZigZagConversion solver = new ZigZagConversion();
        System.out.println(solver.convert("PAYPALISHIRING", 3)); // PAHNAPLSIIGYIR
        System.out.println(solver.convert("PAYPALISHIRING", 4)); // PINALSIGYAHRPI
    }
}

Complexity Analysis

Simulation Approach

Time Complexity: O(n), where n is the length of the input string. Each character is visited exactly once and appended to a row buffer.

Space Complexity: O(n). The row buffers collectively hold all n characters. In languages with immutable strings, the final concatenation may require additional temporary space, but the asymptotic bound remains O(n).

Visit by Row Approach

Time Complexity: O(n). Although there are nested loops, the inner loop advances by cycleLen each iteration, so the total number of iterations across all rows is proportional to n. Each character is visited at most twice (once for the primary index, once for the secondary index in middle rows), but this is still O(n).

Space Complexity: O(1) extra space beyond the output string, since no auxiliary row buffers are needed. If you count the output string itself, the space is O(n).

Comparison Summary

• Simulation: Easier to reason about, slightly more memory due to row buffers, same asymptotic time.
• Visit by row: More mathematical, uses less auxiliary memory, requires understanding the cycle formula.
• Both approaches handle the edge case numRows = 1 by returning the original string immediately, since a single row means no zigzag occurs.

Best Practices

• Handle edge cases first: Always check for numRows === 1 and strings shorter than numRows. Without this guard, the simulation can produce incorrect results or the cycle formula can divide by zero when cycleLen becomes zero.
• Use efficient string building: Avoid repeated string concatenation in languages where strings are immutable. Use StringBuilder in Java, lists in Python, and array joins in JavaScript.
• Prefer the visit-by-row approach for large inputs: When memory is constrained, the index arithmetic approach avoids allocating row buffers and is often faster in practice due to better cache locality.
• Test with diverse inputs: Verify your solution with single-character strings, single-row inputs, strings exactly as long as numRows, and large inputs to ensure correctness and performance.
• Document the cycle formula: The formula cycleLen = 2 * numRows - 2 is not immediately obvious. Add a comment explaining that each full zigzag cycle contains one downward pass of numRows characters and one upward pass of numRows - 2 characters (excluding the shared endpoints).
• Consider readability over micro-optimization: In most real-world scenarios, the simulation approach is perfectly adequate. Choose the approach that your team can maintain and understand easily.

Common Pitfalls

One frequent mistake is forgetting that the upward pass excludes the first and last rows. When moving upward, the top and bottom rows are only visited once per cycle, while middle rows are visited twice. The visit-by-row solution accounts for this with the condition row !== 0 && row !== numRows - 1 before adding the second character.

Another pitfall is off-by-one errors in the cycle index calculation. The second character in a cycle for row i is at index j + cycleLen - i, not j + cycleLen - i - 1. Always verify with a small example before trusting the formula.

Finally, be careful with the direction toggle in the simulation approach. The toggle must happen after appending the character but the check uses the current row. Reversing the order of operations can cause the pointer to move incorrectly and produce garbled output.

Conclusion

The ZigZag Conversion problem is a deceptively simple exercise that rewards both careful simulation and mathematical insight. By exploring multiple solutions — from the intuitive row-buffer simulation to the elegant index-arithmetic approach — you gain a deeper understanding of how visual patterns map to algorithmic logic. Both solutions achieve linear time complexity, but they differ in space usage and readability, giving you the flexibility to choose the right tool for each context. Whether you encounter this problem in an interview or in a real-world data transformation task, the principles of cycle detection, index computation, and efficient string building will serve you well across a wide range of algorithmic challenges.