6. Zigzag Conversion

Walk through the string appending each character to the current row, bouncing the row index up and down between the top and bottom rows. Concatenating the rows top to bottom gives the zigzag reading.

Idea

Rather than compute grid coordinates, just simulate the zigzag walk. Maintain the current row and a direction. Each character goes into the current row; when we hit the top (row 0) or bottom (row numRows-1), we flip direction. Reading the rows in order reconstructs the answer.

Algorithm

1. If numRows == 1, the zigzag is the string itself — return it.
2. Keep rows[numRows] buffers, cur = 0, step = -1.
3. For each character: append to rows[cur]. If cur is 0 or numRows-1, flip step. Then cur += step.
4. Concatenate all rows.

Worked example: s = "PAYPALISHIRING", numRows = 3

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

Joined → "PAHNAPLSIIGYIR".

Complexity

• Time: O(n).
• Space: O(n) for the row buffers.

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        int cur = 0, step = -1;
        for (int i = 0; i < s.length(); i++) {
            rows[cur].append(s.charAt(i));
            if (cur == 0 || cur == numRows - 1) {
                step = -step;
            }
            cur += step;
        }
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        return result.toString();
    }
}