Solving ZigZag Conversion in Python: Step-by-Step Guide

Introduction to ZigZag Conversion

The ZigZag Conversion problem is one of the most popular algorithmic challenges, famously known as LeetCode Problem #6. The task is deceptively simple: given a string and a number of rows, you must arrange the characters of the string in a zigzag pattern across those rows, then read the pattern row by row to produce the output string.

For example, the string "PAYPALISHIRING" written in a zigzag pattern across 3 rows looks like this:

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

Reading line by line, the converted output becomes "PAHNAPLSIIGYIR". While the problem may seem like a brainteaser at first glance, it teaches fundamental concepts about pattern recognition, index manipulation, and simulation techniques that are essential for any developer.

Why It Matters

You might wonder why this problem is worth studying. After all, you are unlikely to encounter a real-world scenario where you need to convert text into a zigzag pattern. However, the value of this problem lies in the problem-solving skills it develops:

Pattern recognition: Identifying mathematical relationships between indices and rows.
Simulation: Modeling a visual process programmatically.
Edge case handling: Dealing with single-row inputs, empty strings, and strings shorter than the number of rows.
Optimization thinking: Moving from a brute-force simulation to a mathematical formula-based solution.

These skills transfer directly to more complex problems involving matrix traversal, string manipulation, and algorithmic optimization. Mastering this problem builds a foundation for tackling harder challenges in coding interviews and competitive programming.

Understanding the ZigZag Pattern

Before writing any code, it is crucial to understand how the zigzag pattern is constructed. Let us examine the string "PAYPALISHIRING" with numRows = 4:

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

Notice the structure. The characters first go downward from row 0 to row 3, then move diagonally upward from row 3 back to row 0. This cycle repeats until all characters are placed. Each complete cycle consists of going down numRows characters and then going up numRows - 2 characters (excluding the first and last rows, which are shared between cycles).

The total length of one full cycle is numRows + (numRows - 2) = 2 * numRows - 2. This value, often called the cycle length, is the key to the mathematical approach we will explore later.

Edge Cases to Consider

If numRows is 1, the output is identical to the input because there is no zigzag possible.
If numRows is greater than or equal to the length of the string, the output is also identical to the input.
If the input string is empty, return an empty string immediately.

Approach 1: Simulation with Row Tracking

The most intuitive approach is to simulate the zigzag process. We create a list of strings, one for each row, and iterate through the input string character by character. We track the current row and a direction flag. When we reach the top or bottom row, we reverse the direction.

Step-by-Step Logic

Create a list of numRows empty strings, one per row.
Initialize current_row = 0 and going_down = True.
For each character in the input string, append it to the string at current_row.
If current_row is 0, set going_down = True. If current_row is numRows - 1, set going_down = False.
Update current_row by adding 1 if going down, or subtracting 1 if going up.
After processing all characters, join all row strings together.

Implementation

def convert_simulation(s: str, numRows: int) -> str:
    # Handle edge cases
    if numRows == 1 or numRows >= len(s):
        return s
    
    # Create a list of strings for each row
    rows = [''] * numRows
    current_row = 0
    going_down = True
    
    for char in s:
        rows[current_row] += char
        
        # Change direction at the boundaries
        if current_row == 0:
            going_down = True
        elif current_row == numRows - 1:
            going_down = False
        
        # Move to the next row
        if going_down:
            current_row += 1
        else:
            current_row -= 1
    
    # Concatenate all rows
    return ''.join(rows)


# Test the function
s = "PAYPALISHIRING"
numRows = 3
result = convert_simulation(s, numRows)
print(f"Input: {s}, numRows={numRows}")
print(f"Output: {result}")
# Output: PAHNAPLSIIGYIR

numRows = 4
result = convert_simulation(s, numRows)
print(f"Input: {s}, numRows={numRows}")
print(f"Output: {result}")
# Output: PINALSIGYAHRPI

Complexity Analysis

This simulation approach has a time complexity of O(n), where n is the length of the input string, because we visit each character exactly once. The space complexity is O(n) as well, since we store all characters across the row strings. This is efficient and easy to understand, making it an excellent solution for interviews.

Approach 2: Mathematical Index Calculation

For those who enjoy a more mathematical approach, we can calculate exactly which characters belong to each row without simulating the traversal. This method leverages the cycle length we discussed earlier.

The Key Insight

Recall that the cycle length is cycle = 2 * numRows - 2. For each row r, the characters come from two positions within each cycle:

The first character is at index r within the cycle.
The second character (if it exists and the row is not the first or last) is at index cycle - r within the cycle.

By iterating over cycles and computing these indices, we can build each row directly.

Implementation

def convert_mathematical(s: str, numRows: int) -> str:
    # Handle edge cases
    if numRows == 1 or numRows >= len(s):
        return s
    
    n = len(s)
    cycle = 2 * numRows - 2
    result = []
    
    for r in range(numRows):
        # Iterate through each cycle
        for i in range(0, n - r, cycle):
            # First character in the cycle for this row
            result.append(s[i + r])
            
            # Second character (middle rows only)
            if r != 0 and r != numRows - 1:
                second_index = i + cycle - r
                if second_index < n:
                    result.append(s[second_index])
    
    return ''.join(result)


# Test the function
s = "PAYPALISHIRING"
print(convert_mathematical(s, 3))  # PAHNAPLSIIGYIR
print(convert_mathematical(s, 4))  # PINALSIGYAHRPI
print(convert_mathematical("A", 1))  # A
print(convert_mathematical("AB", 1))  # AB

Complexity Analysis

The time complexity is O(n) because each character is visited exactly once across all rows and cycles. The space complexity is O(n) for storing the result list. While the complexity is the same as the simulation approach, this method avoids the overhead of direction tracking and may be slightly faster in practice due to fewer conditional checks per character.

Approach 3: Using a Direction Variable (Cleaner Simulation)

A variation of the simulation approach uses a direction variable that is either +1 or -1, making the code more concise. This is a common pattern seen in many accepted solutions on LeetCode.

def convert_direction(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s
    
    rows = [''] * numRows
    current_row = 0
    direction = 1  # 1 means going down, -1 means going up
    
    for char in s:
        rows[current_row] += char
        
        # Reverse direction at boundaries
        if current_row == 0:
            direction = 1
        elif current_row == numRows - 1:
            direction = -1
        
        current_row += direction
    
    return ''.join(rows)


# Comprehensive tests
test_cases = [
    ("PAYPALISHIRING", 3, "PAHNAPLSIIGYIR"),
    ("PAYPALISHIRING", 4, "PINALSIGYAHRPI"),
    ("A", 1, "A"),
    ("AB", 1, "AB"),
    ("ABC", 2, "ACB"),
    ("ABCDE", 4, "ABCED"),
]

for s, rows, expected in test_cases:
    result = convert_direction(s, rows)
    status = "PASS" if result == expected else "FAIL"
    print(f"[{status}] convert('{s}', {rows}) = '{result}' (expected '{expected}')")

Comparing the Approaches

Let us compare the three approaches side by side to help you choose the right one for your needs:

Simulation (Approach 1): Most intuitive and easiest to explain. Ideal for interviews where clarity matters more than brevity.
Mathematical (Approach 2): Most elegant and demonstrates deep understanding of the pattern. Good for impressing interviewers or optimizing for minimal branching.
Direction Variable (Approach 3): A cleaner version of the simulation. The direction variable simplifies the logic and reduces code duplication.

All three approaches have the same asymptotic complexity, so the choice largely comes down to readability and personal preference.

Best Practices

Always Handle Edge Cases First

The most common mistake in this problem is forgetting to handle the case where numRows == 1. Without this check, the simulation approaches will enter an infinite loop or produce incorrect results because the direction never changes. Always place edge case checks at the very beginning of your function.

# Always start with edge case checks
if numRows == 1 or numRows >= len(s) or not s:
    return s

Use Meaningful Variable Names

Avoid single-letter variable names like i, j, or r in production code. Use descriptive names such as current_row, cycle_length, and direction to make your code self-documenting.

Test with Diverse Inputs

Create a comprehensive test suite that covers various scenarios:

def run_tests(func):
    tests = [
        # (input, numRows, expected_output)
        ("PAYPALISHIRING", 3, "PAHNAPLSIIGYIR"),
        ("PAYPALISHIRING", 4, "PINALSIGYAHRPI"),
        ("", 3, ""),
        ("A", 1, "A"),
        ("AB", 1, "AB"),
        ("ABC", 2, "ACB"),
        ("ABCD", 2, "ACBD"),
        ("ABCDE", 4, "ABCED"),
        ("PAYPALISHIRING", 1, "PAYPALISHIRING"),
        ("PAYPALISHIRING", 100, "PAYPALISHIRING"),
    ]
    
    all_passed = True
    for s, numRows, expected in tests:
        result = func(s, numRows)
        if result != expected:
            print(f"FAIL: convert('{s}', {numRows}) = '{result}', expected '{expected}'")
            all_passed = False
    
    if all_passed:
        print("All tests passed!")
    return all_passed

run_tests(convert_simulation)
run_tests(convert_mathematical)
run_tests(convert_direction)

Avoid String Concatenation in Loops When Possible

In Python, string concatenation with += creates a new string each time, which can be inefficient for very large inputs. For maximum performance, consider using lists and joining them at the end:

def convert_optimized(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s
    
    rows = [[] for _ in range(numRows)]
    current_row = 0
    direction = 1
    
    for char in s:
        rows[current_row].append(char)
        if current_row == 0:
            direction = 1
        elif current_row == numRows - 1:
            direction = -1
        current_row += direction
    
    return ''.join(''.join(row) for row in rows)

This version uses lists internally, which have O(1) amortized append time, making it slightly more efficient for very large strings.

Common Pitfalls and How to Avoid Them

Forgetting the numRows == 1 check: This is the number one cause of bugs. Without it, the direction logic breaks because row 0 and the last row are the same.
Off-by-one errors in the mathematical approach: Always verify that computed indices are within bounds before accessing the string.
Confusing row order: Remember that the output is read top to bottom, left to right. The first row in the zigzag is the first part of the output.
Mishandling the middle rows: In the mathematical approach, only the first and last rows have one character per cycle. All middle rows have two.

Conclusion

The ZigZag Conversion problem is an excellent exercise in pattern recognition, simulation, and algorithmic thinking. We explored three distinct approaches: a straightforward simulation with row tracking, a mathematical index calculation method, and a cleaner simulation using a direction variable. Each approach runs in O(n) time and space, but they differ in readability and elegance. The key takeaways are to always handle edge cases upfront, understand the underlying cycle structure, and write clear, well-tested code. By mastering this problem, you strengthen the foundational skills needed to tackle more complex string manipulation and matrix traversal challenges in your development career.