Cracking the Zigzag Conversion Problem

Cracking the Zigzag Conversion Problem: From Brute-Force to Optimal

When it comes to solving string problems efficiently in technical interviews, Zigzag Conversion is a classic example that tests your ability to simulate patterns and then optimize with math. 

As a software engineer deeply immersed in Data Structures and Algorithms (DSA), I’ll guide you step-by-step—from a basic simulation to a clean, optimal solution.

Whether you're preparing for interviews or want to stop thinking brute-force and start recognizing patterns, this article will break things down so clearly, even a 2-year-old could follow.

What Is Zigzag Conversion?

Given a string and a number of rows, we want to write the characters in a zigzag pattern and then read them row by row.

Problem Statement:

Input: s = "PAYPALISHIRING", numRows = 3

Zigzag Write:

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

Output Read:

Output: "PAHNAPLSIIGYIR"

Brute-Force: Simulating the Zigzag

This version simulates the zigzag path. It's the most intuitive approach and perfect for building understanding before optimization.

def zigzag_brute_force(s: str, numRows: int) -> str:
    """
    Brute-force zigzag conversion by simulating the writing direction.
    """
    if numRows == 1 or numRows >= len(s):
        return s

    rows = ['' for _ in range(numRows)]
    curr_row = 0
    going_down = False

    for char in s:
        rows[curr_row] += char
        if curr_row == 0 or curr_row == numRows - 1:
            going_down = not going_down
        curr_row += 1 if going_down else -1

    return ''.join(rows)

Time & Space Complexity:

• Time: O(n)

• Space: O(n) for storing row buffers

Visualization:

Row 0: P   A   H   N
Row 1: A P L S I I G
Row 2: Y   I   R

Transition to the Optimal Version

Brute-force is readable but slow in memory. Let’s optimize.

Key Insight:

We can compute the positions of characters that belong to each row instead of simulating the path.

Pattern:

• Characters repeat every cycle = 2 * (numRows - 1)

• For middle rows, we get one extra diagonal element

Optimal Zigzag Conversion with Math

def zigzag_optimized(s: str, numRows: int) -> str:
    """
    Optimal zigzag conversion using calculated character positions.
    Avoids extra space by appending characters directly.
    """
    if numRows == 1 or numRows >= len(s):
        return s

    result = []
    cycle_len = 2 * (numRows - 1)

    for row in range(numRows):
        for i in range(row, len(s), cycle_len):
            result.append(s[i])
            # Add the diagonal character for middle rows
            diag = i + cycle_len - 2 * row
            if 0 < row < numRows - 1 and diag < len(s):
                result.append(s[diag])

    return ''.join(result)

Time & Space Complexity:

• Time: O(n)

• Space: O(n) for result list, no extra space per row

Another simpler way to write the optimal code is as follows:

def zigzag(s: str, n: int)->str:
    if n ==1: return s

    res =""
    for r in range(n):
        increment = 2 * (n -1)
        for i in range(r, len(s), increment):
            res += s[i]
            if (r > 0 and r < n -1 and
                i + increment -2 *r < len(s)):
                res += s[i + increment -2 * r]
    return res

Tests

print("Expectation : AB, Actual", zigzag("AB", 1))
print("Expectation : ACB, Actual", zigzag("ABC", 2))
print("Expectation : PAHNAPLSIIGYIR, Actual", zigzag("PAYPALISHIRING", 3))
print("Expectation : , Actual", zigzag("A"*100000, 2))
print("Expectation : , Actual", zigzag("ABCDE"*20000, 5))

How to Recognize This Pattern in Other Problems

1. Look for repeating structures or shapes in grid-like problems

2. Notice if characters fall into cycles (like the 2D wave)

3. Try simulating first to understand the shape, then generalize using math

This problem mimics a diagonal + straight row pattern, common in dynamic programming, matrix problems, and encoding tasks.

So What Should You Do Now?

Now that you understand both brute-force and optimal strategies for Zigzag Conversion:

• Practice identifying patterns in string or matrix-based problems

• Re-implement both versions from memory

• Move on to similar problems like Spiral Matrix, Diagonal Traversal, or N-Queens

Let’s stop thinking brute-force and start thinking like optimal problem solvers!