Problem Statement

Given a string s and an integer numRows, rearrange the characters of s into a zigzag pattern across numRows horizontal rows, reading top-to-bottom and left-to-right. Then concatenate all rows from top to bottom to produce the transformed string.

For example, with s = "PAYPALISHIRING" and numRows = 3, the layout is:

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

Resulting in: "PAHNAPLSIIGYIR".

Implement convert(s: str, numRows: int) -> str.

Examples

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

• Input: s = "PAYPALISHIRING", numRows = 4
  Output: "PINALSIGYAHRPI"
  Layout:

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

• Input: s = "A", numRows = 1
  Output: "A"

Approach

When numRows == 1 or numRows >= len(s), no reordering occurs — return s directly.

Otherwise, observe that the zigzag pattern repeats every cycle = 2 * numRows - 2 characters. Within each cycle:

• The first numRows characters fill vertically downward (rows 0 to numRows - 1).
• The next numRows - 2 chaarcters move diagonally upward-right (sikpping top and bottom rows), ending at row 1, column +1.

Instead of allocating a full 2D grid, simulate row-wise accumulation using a list of numRows strings. Track current row index row and direction step: +1 when moving down, -1 when moving up. Flip step at boundaries (row == 0 or row == numRows - 1). Append each character to its corresponding row string.

Optimized Implementation

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

    rows = [''] * numRows
    row_idx = 0
    step = 1

    for char in s:
        rows[row_idx] += char
        if row_idx == 0:
            step = 1
        elif row_idx == numRows - 1:
            step = -1
        row_idx += step

    return ''.join(rows)

Complexity Analysis

• Time Complexity: O(n), where n = len(s). Each character is visited exact once.
• Space Complexity: O(n), for storing the numRows accumulated strings (total length equals n).