Zigzag Conversion

Problem

Write a string in a zigzag pattern across a given number of rows, then read it row by row.

Input:  s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Python Solution

def convert_zigzag(s, num_rows):
    if num_rows == 1:
        return s
    rows = [""] * num_rows
    current_row = 0
    step = -1
    for ch in s:
        rows[current_row] += ch
        if current_row == 0 or current_row == num_rows - 1:
            step = -step
        current_row += step
    return "".join(rows)

C++ Solution

string convertZigzag(string s, int numRows) {
    if (numRows == 1) return s;
    vector<string> rows(numRows);
    int currentRow = 0, step = -1;
    for (char ch : s) {
        rows[currentRow] += ch;
        if (currentRow == 0 || currentRow == numRows - 1) step = -step;
        currentRow += step;
    }
    string result;
    for (string& row : rows) result += row;
    return result;
}

Java Solution

class Solution {
    public String convertZigzag(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 currentRow = 0, step = -1;
        for (char ch : s.toCharArray()) {
            rows[currentRow].append(ch);
            if (currentRow == 0 || currentRow == numRows - 1) step = -step;
            currentRow += step;
        }
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) result.append(row);
        return result.toString();
    }
}

Complexity

Time: O(n) — each character is placed into its row exactly once. Space: O(n) — the row buffers together hold every character of the input.