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:

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

Visualization and 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.

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

Flipping only at the two edges is what keeps the walk inside the array. goingDown starts false, so the first character, which lands on row 0, flips it to true and the walk starts downward. Every later arrival at row 0 or row numRows-1 flips it again, turning the walk around before currentRow can step out of range. That is why no bounds check is needed when reading rows[currentRow].

Visualization and 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.

Intuition

The zigzag pattern repeats every cycleLen = 2 * numRows - 2 characters. Rather than tracking where each cycle starts, let j walk a single row directly: it begins at index row and advances by cycleLen, which lands on exactly that row's downward-leg characters.

The upward-leg offset comes from the geometry of the V. The character at j sits row steps below the top on the way down. Its partner on the way back up sits the same row steps below the top, which is cycleLen - 2 * row positions further along the string. 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 read characters directly from the original string, with no simulation and no extra lists.

Algorithm

Visualization and Code