AlgoMaster Logo

Zigzag Conversion

mediumFrequency12 min readUpdated June 23, 2026

Understanding the Problem

The zigzag pattern places characters top-to-bottom in a column, then diagonally upward until they reach the top row again, then top-to-bottom again, and so on. This creates a "V" shape that repeats.

For numRows = 4, the placement order looks like this:

The characters go down rows 0 through 3, then back up through rows 2 and 1, then down again. That down-and-up cycle has a length of 2 * numRows - 2. For 4 rows, the cycle length is 6. This cycle length drives every efficient solution below.

When numRows = 1 or numRows >= len(s), the zigzag pattern equals the original string and no rearrangement happens. Every solution handles this case with an early return.

Key Constraints:

  • 1 <= numRows <= 1000 → numRows can exceed the string length. In that case, every character occupies its own row and the output equals the input, which is why each approach starts with the numRows >= len(s) early return.
  • 1 <= s.length <= 1000 → The output is a permutation of the input, so the answer always fits in a fixed-width integer index. No overflow concerns arise even with the index arithmetic in Approach 3.

Approach 1: Simulation with 2D Grid

Intuition

Simulate the zigzag directly. Create a 2D grid, place each character in its cell by moving down and then diagonally up, then read the grid row by row.

This mirrors drawing the pattern on paper. It is straightforward to reason about, but it wastes space because most cells in the grid stay empty.

Algorithm

  1. If numRows is 1 or greater than or equal to the string length, return the string as-is.
  2. Create a 2D grid with numRows rows and n columns, initialized to empty.
  3. Walk through the string. Start at row 0, column 0. Move downward. When you hit the bottom row, switch to moving diagonally up-right. When you hit the top row, switch back to moving straight down.
  4. After placing all characters, read the grid row by row, skipping empty cells, to build the result.

Example Walkthrough

Trace s = "PAYPALISHIRING" with numRows = 3. The cycle moves down to row 2, then up to row 0, repeating. Each step shows the placed character and the cell it lands in (row, col):

The grid now holds:

Reading row 0 gives PAHN, row 1 gives APLSIIG, row 2 gives YIR. Concatenating produces PAHNAPLSIIGYIR, the expected output.

Code

The bottleneck is the 2D grid. We allocate numRows * n cells, but only n of them ever hold a character. The column of each character is irrelevant to the final answer, since we read row by row. The next approach drops the grid and tracks only each character's row, appending it directly to a per-row list.

Approach 2: Row-by-Row Collection

Intuition

Instead of a full 2D grid, use one list (or StringBuilder) per row. While iterating through the string, track which row the current character belongs to and append it there. The row bounces between 0 and numRows-1 exactly as in the simulation, but the wasted columns disappear.

The result is the same reading order as Approach 1, with O(n) space instead of O(n * numRows).

Algorithm

  1. If numRows is 1 or greater than or equal to the string length, return the string as-is.
  2. Create an array of numRows empty strings (or StringBuilders).
  3. Initialize currentRow = 0 and direction = 1 (going down).
  4. For each character in the string:
    • Append it to the list for currentRow.
    • If currentRow is 0, set direction to +1 (down). If currentRow is numRows-1, set direction to -1 (up).
    • Update currentRow += direction.
  5. Concatenate all row lists to form the result.

The check order on lines if currentRow == 0 ... else if currentRow == numRows - 1 matters. We append the character first, then decide the direction for the next step. Resetting direction to +1 at the top and -1 at the bottom guarantees the index never moves past row 0 or row numRows-1, so no bounds check is needed when reading rows[currentRow].

Example Walkthrough

Trace s = "PAYPALISHIRING" with numRows = 3. Start at currentRow = 0, direction = 1:

The three rows end up holding PAHN, APLSIIG, and YIR. Concatenating them gives PAHNAPLSIIGYIR.

Code

Approach 2 runs in O(n) time, which is optimal since every character must be read at least once. It still uses O(n) extra space for the row lists. For any given row, the indices of the characters that belong to it follow an arithmetic sequence determined by the cycle length. The next approach computes those indices directly and writes straight to the output, removing the per-row lists.

Approach 3: Direct Index Calculation

Intuition

The zigzag pattern repeats every cycle = 2 * numRows - 2 characters. Let j step through the cycle start indices 0, cycle, 2*cycle, .... Within each cycle, every row receives characters at fixed offsets from j:

  • Row 0 (top): one character per cycle, at index j
  • Row numRows-1 (bottom): one character per cycle, at index j + (numRows - 1)
  • Middle row i: two characters per cycle, at indices j + i (downward leg) and j + cycle - i (upward leg)

The upward-leg index comes from the geometry of the V. On the way down, row i sits i steps below the top. On the way back up, the same row sits i steps below the top again, which is cycle - i steps after the cycle start, since the full cycle has length cycle. Top and bottom rows lie on the fold of the V, so they appear only once per cycle and have no separate upward character. This lets us iterate row by row and read characters directly from the original string, with no simulation and no extra lists.

Algorithm

  1. If numRows is 1 or greater than or equal to the string length, return the string as-is.
  2. Compute cycle = 2 * numRows - 2.
  3. For each row i from 0 to numRows-1:
    • For each cycle starting index j = 0, cycle, 2*cycle, ...:
      • Append s[j + i] if it's within bounds (this is the "down" character).
      • If i is not the first or last row, also append s[j + cycle - i] if within bounds (this is the "up" character).
  4. Return the accumulated result.

Example Walkthrough

Trace s = "PAYPALISHIRING" with numRows = 3, so cycle = 4. The character indices are:

Row 0 (top, down index j only):

Row 0 contributes PAHN.

Row 1 (middle, down index j + 1 and up index j + 4 - 1 = j + 3):

Row 1 contributes APLSIIG.

Row 2 (bottom, down index j + 2 only):

Row 2 contributes YIR.

Concatenating the rows in order gives PAHN + APLSIIG + YIR = PAHNAPLSIIGYIR, matching Approaches 1 and 2.

Code