Zigzag Conversion

Practice Link

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

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

Read line by line, the result is "PAHNAPLSIIGYIR". Given a string s and a number of rows, return the converted string.

Key Idea#

Calculating the mathematical interval of the zigzag pattern to simulate the row-by-row traversal.

Intuition#

Instead of actually drawing the zigzag, observe that if you walk through the string and track which row each character belongs to, you can bucket the characters into numRows strings and join them at the end.

The row index starts at 0, goes down to numRows - 1, then bounces back up to 0 — a repeating V-shape. Track the current row and a direction flag (+1 or -1), flipping direction whenever you hit the top or bottom row.

Edge case: if numRows == 1 (or numRows >= s.length()), the zigzag is flat — just return s directly.

Optimal Solution#

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length();
        if(numRows == 1)
            return s;

        string res = "";
        for(int r = 0; r < numRows; r++){
            int inc = (numRows-1) * 2;
            for(int i = r; i < n; i += inc){
                res += s[i];
                if(r > 0 && r < numRows-1 && i + inc - (2*r) < n){
                    res += s[i + inc - (2*r)];
                }
            }
        }
        return res;
    }
};

How it works:

• The full zigzag cycle has length inc = (numRows - 1) * 2.
• For each row r, the first character in a cycle is at index r, then r + inc, r + 2*inc, …
• Middle rows (r > 0 && r < numRows - 1) also have a diagonal character between two cycle anchors. Its index inside the cycle is inc - 2*r after the anchor.
• Top row (r == 0) and bottom row (r == numRows - 1) have no diagonal character — the cycle gaps are even, so only the anchor applies.

Example — numRows = 4, s = "PAYPALISHIRING":

P         I    N       ← row 0: every 6th char
A    L    S    I  G   ← row 1: anchor + diagonal 4 apart
Y  A      H  R        ← row 2: anchor + diagonal 2 apart
P         I           ← row 3: every 6th char

Output: "PINALSIGYAHRPI"

Time Complexity: O(n) — every character is visited exactly once.

Space Complexity: O(n) — the result string.

Follow Up#

What if you needed to support Unicode strings (multi-byte characters)?#

The current solution indexes into s by byte position using s[i], which is correct for ASCII. For a Unicode string (e.g., emojis or CJK characters), you'd need to work with a character array (or iterator over code points) rather than raw byte indices, since a single character can span multiple bytes in UTF-8.