Abstract / Summary

Convert a string into a zigzag pattern on multiple rows and read it out row by row to form a new string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (4+ million submissions).

Typical patterns to solve this problem:

• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method that rearranges a given string into a zig-zag pattern with a specified number of rows and then reads the characters row by row to produce a new string. The algorithm processes the input in a single linear pass, dynamically tracking the current row and direction of movement, and accumulates characters for each row in a dictionary.

Core Logic

The method begins by handling the trivial situation where the number of rows equals one. In that case the zig-zag pattern collapses to a straight line, so the original string is returned unchanged.

if numRows == 1:
    return s

Two integer variables, y and delta, are introduced to represent the current row index and the step direction, respectively. y starts at the top row (index 0) and delta is initially set to +1, indicating a downward movement.

y = 0
delta = +1

A defaultdict of strings, named rows, is created to collect characters belonging to each row without needing explicit existence checks.

rows = defaultdict(str)

The main loop iterates over each character c in the input string. For each character, the algorithm appends it to the string associated with the current row y. Afterwards, y is updated by adding delta, moving the cursor to the next row in the current direction.

for c in s:
    rows[y] += c
    y += delta

When the cursor steps beyond the top or bottom boundary (y < 0 or y == numRows), the direction must reverse. The code accomplishes this by moving the cursor back two steps in the opposite direction and flipping the sign of delta. This adjustment ensures that the next iteration places the character in the correct row after the turn.

    if y < 0 or y == numRows:
        y -= 2 * delta
        delta = -delta

After all characters have been placed, the rows are concatenated in order of their natural dictionary insertion (which follows the numeric row keys) to form the final transformed string.

return "".join(rows.values())

Edge Cases

The implementation explicitly handles the case where numRows is one. In that scenario the zig-zag pattern degenerates to a single line, and the method returns the input string directly, avoiding unnecessary processing.

Another subtle edge condition occurs when the cursor reaches the limits of the row range. The conditional if y < 0 or y == numRows captures both the upper overflow (when moving upward past the first row) and the lower overflow (when moving downward past the last row). By subtracting 2 * delta from y, the algorithm steps back onto the last valid row before reversing direction, guaranteeing that no character is assigned to an invalid row index.

Performance Optimizations

The algorithm achieves high efficiency by performing a single traversal of the input string. Each character is processed exactly once, and the row accumulation uses in-place string concatenation within the defaultdict. This avoids the overhead of repeatedly checking for the existence of a row key, as the defaultdict automatically creates an empty string for any new row index.

Because the rows are stored as separate strings, the final concatenation step simply joins these pre-built substrings, which is faster than repeatedly inserting characters into a single mutable buffer. The use of integer arithmetic for direction changes (delta = -delta) and the compact boundary correction (y -= 2 * delta) eliminates the need for more complex conditional structures, keeping the inner loop tight and cache-friendly.

Overall, the design balances clarity with low-level efficiency, delivering a solution that scales well with the length of the input string and the number of rows.

Imagine you have a long, colorful train of letters and you want to stack them up in a special shape to make a zigzag pattern that goes up and down a hill.

First, look at the number of rows. If the number is one, the train just stays in a single line, so there is nothing to move and the letters stay exactly as they were.

If there are more rows, imagine holding a magic crayon that draws a zigzag path. Start at the very top row and place a letter. Move down to the next row and place the next letter. Keep moving down row by row until the bottom is reached. Once the bottom is hit, it is time to bounce back up, just like a ball hitting the floor and hopping back toward the sky.

As the letters are placed, they are tucked into different piles based on which row they belong to. The crayon keeps track of whether it is heading down toward the bottom or climbing back up toward the top. If the path hits the bottom row or the very top, the direction changes, and the crayon starts moving the other way.

After every single letter from the original train has been placed into its new row, all the piles are lined up neatly side by side. The final result is a new string of letters that looks different from the start because they have been reordered by the zigzag path.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python									TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	C	Rust	JS	C#		Go		PHP	TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	aylei					Rust
	begeekmyfriend				C
	BigEggStudy							C#
	black-shadows	C++
	charles-wangkai		Java
	chenyanzhe	C++
	everthis						JS
	fengvyi	C++
	fsq	C++
	gaosq0604			Python
	Garvit244			Python
	gouthampradhan		Java
	halfrost									Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007			Python
	luangong	C++
	martianoff								Scala
	qiyuangong		Java
	ruoru					Rust
	Shamik07										Dart
	suxrobGM							C#
	varunu28		Java
	vli02				C
	vthwang		Java
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
fsq	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
martianoff	Scala
qiyuangong	Java
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality