Zigzag Conversion

How it works

Instead of calculating positions mathematically, we can simulate the actual zigzag writing process. We maintain a current row and a direction. As we traverse the string, we place each character in its corresponding row. When we hit the top or bottom row, we reverse direction. This approach directly models how characters would be written in the zigzag pattern.

Steps

1. Handle edge cases where numRows is 1 or greater than or equal to the string length by returning the original string.
2. Create an array of lists (or strings), one for each row.
3. Initialize the current row to 0 and direction to 1 (moving down).
4. For each character in the string:
   • Append the character to the current row's list.
   • Move to the next row by adding the direction.
   • If we reach the first or last row, reverse the direction by multiplying by -1.
5. Concatenate all rows in order and return the result.

Complexity

• Time complexity: O(n)
• Space complexity: O(n) for the output string.

Things to watch for

Not Handling the Single Row Edge Case

When numRows == 1, the zigzag pattern is just the original string. Without this check, the increment becomes 2 * (1 - 1) = 0, causing an infinite loop or division issues.

Incorrect Direction Toggle Logic

When simulating the zigzag traversal, the direction should only flip when reaching the first or last row. A common mistake is toggling direction after every step, or only checking one boundary.

Wrong Index Calculation for Middle Row Diagonal Characters

In the mathematical approach, middle rows have two characters per cycle. The diagonal character position i + increment - 2 * r is often miscalculated, leading to missing characters or index out of bounds errors.

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

        res = [[] for _ in range(numRows)]
        row, dir = 0, 1
        for c in s:
            res[row].append(c)
            row += dir
            if row == 0 or row == (numRows - 1):
                dir *= -1

        return ''.join([''.join(row) for row in res])

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1 || numRows >= s.size()) {
            return s;
        }

        vector<string> res(numRows);
        int row = 0, dir = 1;

        for (char& c : s) {
            res[row] += c;
            row += dir;
            if (row == 0 || row == numRows - 1) {
                dir *= -1;
            }
        }

        string result;
        for (string& rowString : res) {
            result += rowString;
        }
        return result;
    }
};