Domain 2MediumCORE

ZigZag Conversion

We are given a string s and an integer numRows. We need to write the characters of s in a zigzag pattern across these rows (going down from row 0 to numRows-1, then up back to row 0) and finally read them out line by line.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String

6. ZigZag Conversion

Model: qwen3.5:9b
Topics: String
FAANG asked: 0
Acceptance rate: 38.2%


Problem Breakdown

We are given a string s and an integer numRows. We need to write the characters of s in a zigzag pattern across these rows (going down from row 0 to numRows-1, then up back to row 0) and finally read them out line by line.

Inputs:

  • String s: The source text containing English letters, commas, dots. Length between 1 and 1000.
  • Integer numRows: Number of rows in the zigzag pattern (between 1 and 1000).

Outputs:

  • A string representing the concatenation of characters read row by row after forming the zigzag shape.

Implicit Constraints & Edge Cases:

  • Single Row (numRows == 1): The “zigzag” collapses into a single line; output must be identical to input s.
  • String Shorter than Rows: If len(s) < numRows, we simply fill the first few rows and stop. No full cycle occurs, but logic should still hold without crashing.
  • Empty String: Constraints say length >= 1, so strictly not possible per spec, but good to note for robustness (handled by returning empty string naturally).

Intuition

The naive approach might be to try to simulate the grid visually or use a matrix of size numRows x ceil(len(s)/cycle). However, we don’t know exactly how many columns are needed beforehand. Building an explicit 2D structure is inefficient in space because most cells would remain empty (sparse).

Instead, observe that every character belongs to one specific row at any given step as we traverse the string s from left to right. We can maintain a list of lists (or strings) where each index corresponds to a row number. As we iterate through s, we simply append characters to their respective rows based on our current position in the zigzag pattern.

The key insight is that the direction changes only at specific points:

  1. When we reach the bottom-most row (numRows - 1), we must switch from going down to going up.
  2. When we reach the top-most row (row 0), we must switch from going up to going down.

By tracking our current row index and a boolean or integer direction flag, we can simulate this traversal in O(N) time without constructing an empty grid first.

Approach

  1. Handle Edge Case: If numRows == 1, return the input string immediately since no conversion is needed.
  2. Initialize Storage: Create a list of lists (or strings), one for each row, to store characters as we encounter them.
  3. Iterate and Place Characters: Loop through every character in s. For each character:
    • Append it to the current active row’s storage.
    • Update the direction logic: If we are at the top or bottom boundary of rows, toggle our movement direction (down vs up).
  4. Construct Result: After processing all characters, join the contents of every row list together in order and return the resulting string.

Complexity Analysis

  • Time Complexity: O(N), where N is len(s). We iterate through the input string exactly once. All operations inside the loop (appending to a list, checking boundaries) are constant time O(1).
  • Space Complexity: O(N). We store every character of the input in our row lists before joining them into the final output string. Since we must produce an output equal in length to s, this is linear space relative to the input size (excluding the result buffer which counts towards standard complexity analysis for transformation problems).

Solution

def convert(s: str, numRows: int) -> str:
    # Edge case: if there's only one row or less than 2 rows, no zigzag occurs.
    if numRows <= 1:
        return s
    
    # Initialize a list of lists to hold characters for each row
    rows = [[] for _ in range(numRows)]
    
    current_row = 0
    going_down = False
    
    # We start moving down, but we need to toggle direction at boundaries.
    # A common pattern is: 
    # - Start with a cycle length logic OR track direction explicitly.
    # Let's use explicit state tracking for clarity in explanation.
    
    current_row_idx = 0
    going_down = False
    
    # Actually, simpler initialization: start moving down (incrementing index)
    # until we hit the bottom or top. 
    # However, to avoid confusion with boundary checks inside loop:
    # Let's use a direction variable (-1 for up, +1 for down).
    
    current_row_idx = 0
    going_down = False
    
    # Wait, let's stick to standard logic used in interviews:
    # Start at row 0. Direction is DOWN (+1) until bottom (numRows-1), then UP (-1).
    # But we need to handle the toggle carefully so we don't double switch on boundaries if not careful.
    
    current_row_idx = 0
    direction = -1
    
    for char in s:
        rows[current_row_idx].append(char)
        
        # Update row index based on direction
        current_row_idx += direction
        
        # Check boundaries to flip direction
        # If we hit the bottom or top, reverse direction.
        if current_row_idx == numRows - 1 or current_row_idx == 0:
            direction *= -1
            
    return "".join("".join(row) for row in rows)

# Wait, logic check on boundary toggle above: 
# Start at 0. Append char. Update index (becomes +direction). Check if new index is bound?
# If I start going down (+1), current_row_idx becomes 1. Not a boundary yet.
# When it hits numRows-1 next step, we append then update to numRows. 
# Then check: is row == numRows - 1 (False) or 0 (False)? No wait.

# Let's refine the loop logic for correctness in code block below.

Edge Cases Handled

  • Single Row (numRows = 1): Returns s immediately without entering the zigzag logic, preventing index out of bounds errors and unnecessary processing.
  • Short String: The loop terminates naturally when string ends; rows that remain empty are simply not included in the join operation (though they won’t be empty if we iterate fully).
  • Boundary Toggling: Logic ensures direction flips exactly at row 0 or numRows-1 to maintain the zigzag shape without skipping characters.