LeetCode 6 · Matrix & strings

ZigZag Conversion, explained with a picture

Letters walking down and up a staircase.

Matrix & strings
▶ Watch it step by step

The problem

Write a string in a zigzag on numRows rows, then read it row by row.

Input:  "PAYPALISHIRING", 3 rows
Output: "PAHNAPLSIIGYIR"

Picture it

Picture letters walking down and up a staircase of rows: down to the bottom row, back up to the top, and so on. Each row collects the letters that land on it; joining the rows gives the answer.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Simulate the row index bouncing between 0 and numRows − 1. O(n).

Python solution

def convert(s, rows):
    if rows == 1:
        return s
    lines = [""] * rows
    r, step = 0, 1
    for ch in s:
        lines[r] += ch
        if r == 0: step = 1
        elif r == rows - 1: step = -1
        r += step
    return "".join(lines)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.