← ~/lc-grind/posts

#6 - Zigzag Conversion

September 26, 2025

Zigzag Conversion

Problem Description

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)


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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:


string convert(string s, int numRows);

Example 1:


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

Example 2:


Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:


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

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Solution

1. Problem Deconstruction

Technical Restatement: Given a string s and integer numRows, rearrange characters in a zigzag pattern across numRows rows. The pattern follows a periodic vertical oscillation: characters are placed sequentially downward to row numRows-1, then upward to row 0, repeating until string exhaustion. The result is the concatenation of all rows from top to bottom.

Beginner Explanation: Imagine writing letters on a series of horizontal lines. You start at the top line, move down to the next line for each new letter until you hit the bottom, then reverse direction and move upward. After writing all letters, read them left-to-right, top-to-bottom.

Mathematical Formulation: Let n = len(s), r = numRows. Define cycle length T = max(1, 2r - 2). For character at index i:

  • Row index: min(i % T, T - i % T)
  • Position in row: floor(i / T) * (r - 1) + adjustment for diagonal movement

Constraint Analysis:

  • 1 <= s.length <= 1000: Permits O(n²) solutions but O(n) achievable. Upper bound small enough for explicit matrix construction.
  • 1 <= numRows <= 1000: Critical edge case when numRows ≥ n creates single-column output. Also handles numRows = 1 (no zigzag).
  • Character set: No special handling needed beyond standard string processing.

2. Intuition Scaffolding

Real-World Metaphor: Like stadium waves - people stand up row by row (downward movement), then sit down in reverse order (upward movement). Recording which rows participated when gives the zigzag sequence.

Gaming Analogy: Think of a side-scroller where enemies appear in diagonal formations. The player’s scanning pattern (left-right, top-down) matches how we read the zigzag.

Math Analogy: A piecewise function mapping linear indices to 2D coordinates with periodic boundary conditions, similar to modular arithmetic on a cylinder.

Common Pitfalls:

  1. Direction Toggle Errors: Forgetting to reverse at boundaries
  2. Row Bounds Mismanagement: Index errors when numRows = 1
  3. Cycle Calculation Oversight: Period is 2r-2 except when r=1
  4. Uneven Column Assumption: Assuming all rows have equal length
  5. Over-Engineering: Building full matrix when direct mapping suffices

3. Approach Encyclopedia

Approach 1: Direction Simulation

def convert(s, numRows):
    if numRows == 1: return s
    rows = [''] * numRows
    row, step = 0, 1
    for char in s:
        rows[row] += char
        if row == 0: step = 1
        elif row == numRows - 1: step = -1
        row += step
    return ''.join(rows)
  • Complexity: Time O(n), Space O(n)
  • Derivation: Each character visited once. String concatenation O(1) amortized.
  • Visualization:
Step 0: row=0 [P]
Step 1: row=1 [P][A]
Step 2: row=2 [P][A][Y]
Step 3: row=1 [P][AP][Y]

Approach 2: Cycle Arithmetic

def convert(s, numRows):
    if numRows == 1: return s
    cycle = 2 * numRows - 2
    rows = [''] * numRows
    for i, char in enumerate(s):
        pos = i % cycle
        row = min(pos, cycle - pos)
        rows[row] += char
    return ''.join(rows)
  • Complexity: Time O(n), Space O(n)
  • Proof: Modular arithmetic O(1) per character
  • Visualization:
Cycle = 4 (for numRows=3)
i=0: pos=0 → row=0
i=1: pos=1 → row=1
i=2: pos=2 → row=min(2,2)=2
i=3: pos=3 → row=min(3,1)=1

Approach 3: Matrix Simulation (Explicit)

def convert(s, numRows):
    if numRows == 1: return s
    matrix = [[''] * len(s) for _ in range(numRows)]
    # ... filling logic with direction changes
    # Flatten row-wise
  • Complexity: Time O(n²), Space O(n²)
  • Use Case: Pedagogical clarity, though inefficient

4. Code Deep Dive

Optimal Solution (Cycle Arithmetic):

def convert(s: str, numRows: int) -> str:
    # Edge case: no zigzag possible
    if numRows == 1 or numRows >= len(s):
        return s
    
    cycle = 2 * numRows - 2  # Period of zigzag pattern
    rows = [''] * numRows    # String builders for each row
    
    for i, char in enumerate(s):
        # Determine position in cycle
        pos = i % cycle
        # Map to row index (symmetric around numRows-1)
        row = pos if pos < numRows else cycle - pos
        rows[row] += char
    
    return ''.join(rows)

Line-by-Line Analysis:

  1. Lines 2-3: Immediate edge case returns avoid unnecessary computation
  2. Line 5: Cycle length derived from zigzag geometry (down r-1, up r-1)
  3. Line 6: Pre-allocate rows for O(1) appends
  4. Line 9: Modular arithmetic finds position in current cycle
  5. Line 11: Min function handles both downward and upward segments
  6. Line 12: Efficient string building per row

Edge Case Handling:

  • numRows=1: Returns original string (no zigzag)
  • numRows ≥ len(s): Single column, equivalent to original order
  • s="A", numRows=3: Cycle logic handles single character correctly

5. Complexity War Room

Hardware-Aware Analysis: At n=1000, storing rows array uses ~4KB (1000 pointers), easily fitting in L1 cache. Cycle arithmetic uses minimal integer operations.

Approach Comparison Table:

Approach Time Space Readability Interview Viability
Direction Sim O(n) O(n) 9/10 ✅ Most intuitive
Cycle Math O(n) O(n) 7/10 ✅ Optimal logic
Matrix Build O(n²) O(n²) 8/10 ❌ Space inefficient

6. Pro Mode Extras

Variants:

  • Zigzag with Variable Amplitude: Modify cycle length dynamically
  • Bidirectional Reading: Read columns in alternating directions
  • 3D Zigzag: Add depth dimension for cubic pattern

Interview Cheat Sheet:

  • First Mention: “This is essentially a periodicity problem with O(n) solution”
  • Key Insight: “Cycle length is 2r-2, mapping is symmetric around the middle”
  • Testing Priority: numRows=1, numRows≥n, small patterns (n=3, r=2)