#6

Medium

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Zigzag Conversion

Convert a string into a zigzag pattern across multiple rows and read it line by line efficiently for string manipulation tasks.

string

Problem Statement

Given a string and a number of rows, write the characters in a zigzag pattern moving down and diagonally up, then read them line by line. The zigzag pattern starts at the top row and moves downward until the bottom row, then diagonally back up to the top repeatedly.

Implement a function that takes the string and number of rows, and returns a new string representing the zigzag reading. For example, converting "PAYPALISHIRING" with 3 rows produces "PAHNAPLSIIGYIR". Ensure your solution handles up to 1000 characters and supports both upper- and lower-case letters along with commas and periods.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Example 2

Input: See original problem statement.

Output: See original problem statement.

string convert(string s, int numRows);

Example 3

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

Example details omitted.

Constraints

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

Solution Approach

Row-wise Simulation

Create an array of strings, one for each row. Iterate through the input string, appending characters to the current row and reversing direction when reaching top or bottom. Finally, concatenate all row strings to obtain the zigzag output.

Index Calculation Method

Use the pattern cycle of length 2*numRows-2 to calculate positions of characters for each row directly. Loop through each row and pick characters at indices determined by the cycle, avoiding extra memory for row storage while maintaining O(n) complexity.

Edge Case Handling

Check for single-row or empty strings to return the input directly. Handle numRows greater than string length and strings with special characters. Ensuring these edge conditions prevents index errors and guarantees correct zigzag reconstruction.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed once, either by appending to row strings or calculating indices. Space complexity is O(n) for storing characters per row and the final concatenated result, matching the input size.

What Interviewers Usually Probe

Watch for off-by-one errors in row traversal during zigzag simulation.
Check whether candidate handles single-row or short strings correctly.
Listen for explanations about string indexing versus direct row concatenation for pattern efficiency.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reverse direction when reaching top or bottom row, breaking the zigzag pattern.
Preallocating insufficient row arrays, causing index errors for large numRows values.
Confusing cycle calculation indices, leading to incorrect concatenation order.

Follow-up variants

Convert a string with custom row patterns like alternating multiple zigzags per cycle.
Implement zigzag reading in a memory-efficient way using a single string buffer and offsets.
Support dynamic row counts determined at runtime, requiring adaptable indexing or row arrays.

FAQ

What is the simplest way to implement Zigzag Conversion for interviews?

Use row-wise simulation with an array of strings and direction flags, then concatenate all rows at the end.

How do I handle numRows greater than the string length?

Return the string directly or treat each character as a separate row since the zigzag pattern collapses.

Can this approach work for very long strings efficiently?

Yes, both row-wise simulation and index calculation operate in O(n) time and O(n) space, scaling linearly with string length.

Is it necessary to use extra arrays for rows?

Not strictly; you can compute character positions with cycle-based index formulas to avoid additional arrays.

How does the string-driven solution strategy apply to Zigzag Conversion?

It focuses on iterating characters in sequence while tracking their target row, aligning perfectly with the zigzag reading requirement.

terminal

Solution

Solution 1: Simulation

We use a 2D array $g$ to simulate the process of arranging the string in a zigzag pattern, where $g[i][j]$ represents the character at row $i$ and column $j$. Initially, $i = 0$. We also define a direction variable $k$, initially $k = -1$, which means moving upwards.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        g = [[] for _ in range(numRows)]
        i, k = 0, -1
        for c in s:
            g[i].append(c)
            if i == 0 or i == numRows - 1:
                k = -k
            i += k
        return ''.join(chain(*g))

Continue Practicing

#5 longest palindromic substring #8 string to integer atoi #3 longest substring without repeating characters