Problem Description

You need to convert a string into a zigzag pattern based on a specified number of rows, then read the pattern line by line to produce a new string.

The zigzag pattern works like this: characters are written diagonally down for numRows rows, then diagonally up (skipping the top and bottom rows), and this pattern repeats.

For example, with the string "PAYPALISHIRING" and numRows = 3:

• Characters are placed in positions forming a zigzag:

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

• Reading line by line gives: "PAHNAPLSIIGYIR"

With numRows = 4, the same string would look like:

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

Reading line by line: "PINALSIGYAHRPI"

The pattern movement is:

1. Start at row 0
2. Move down until reaching the last row (numRows - 1)
3. Move up until reaching the first row (row 0)
4. Repeat steps 2-3 until all characters are placed

Your task is to implement the convert function that takes a string s and an integer numRows, and returns the string after performing this zigzag conversion and reading it line by line.

Special case: When numRows = 1, the zigzag pattern is just the original string itself.

Intuition

The key insight is that we don't need to create a full 2D grid with all the empty spaces. Instead, we can observe that characters move in a predictable pattern - they go down row by row until hitting the bottom, then go up row by row until hitting the top, and repeat.

Think of it like a ball bouncing between two walls. When we place characters:

• We start at row 0 and move downward
• When we hit the bottom row (numRows - 1), we bounce back and start moving upward
• When we hit the top row (0), we bounce again and move downward

This bouncing behavior can be captured with a direction variable. If we use k to represent the direction:

• k = 1 means moving down (increasing row index)
• k = -1 means moving up (decreasing row index)

The crucial observation is that direction changes happen exactly at the boundaries - row 0 and row numRows - 1. At these turning points, we simply flip the direction: k = -k.

Rather than building a complete 2D matrix with spaces, we can use a list of lists where g[i] stores only the characters that belong to row i. As we traverse the string, we:

1. Add the current character to its corresponding row
2. Check if we're at a boundary (top or bottom row)
3. If yes, flip the direction
4. Move to the next row based on the current direction

This approach naturally handles the zigzag pattern without worrying about column positions or spacing, since we only care about the final order when reading line by line.

Solution Approach

Let's walk through the implementation step by step:

1. Handle Edge Case

if numRows == 1:
    return s

When numRows = 1, there's no zigzag pattern - the output is identical to the input string.

2. Initialize Data Structures

g = [[] for _ in range(numRows)]
i, k = 0, -1

• g: A list of numRows empty lists. Each g[i] will collect characters that belong to row i.
• i: Current row index, starting at 0 (first row)
• k: Direction indicator, initially set to -1. This will be flipped to 1 when we start processing the first character.

3. Process Each Character

for c in s:
    g[i].append(c)
    if i == 0 or i == numRows - 1:
        k = -k
    i += k

For each character c in the string:

• Append c to the current row g[i]
• Check if we're at a boundary:
  • i == 0: We're at the top row
  • i == numRows - 1: We're at the bottom row
  • At boundaries, flip the direction: k = -k
• Move to the next row: i += k
  • If k = 1, move down (increment i)
  • If k = -1, move up (decrement i)

4. Build the Result

return ''.join(chain(*g))

• chain(*g): Flattens the list of lists. It unpacks all lists in g and chains them together into a single iterator.
• ''.join(): Concatenates all characters into the final string.

Example Walkthrough with "PAYPALISHIRING", numRows = 3:

Initial state: i = 0, k = -1, g = [[], [], []]

• 'P': Add to g[0]. Since i = 0, flip k to 1. Move to i = 1.
• 'A': Add to g[1]. Not at boundary. Move to i = 2.
• 'Y': Add to g[2]. Since i = 2 (numRows-1), flip k to -1. Move to i = 1.
• 'P': Add to g[1]. Not at boundary. Move to i = 0.
• 'A': Add to g[0]. Since i = 0, flip k to 1. Move to i = 1.

This continues until g = [['P','A','H','N'], ['A','P','L','S','I','I','G'], ['Y','I','R']].

The final join produces: "PAHNAPLSIIGYIR".

Example Walkthrough

Let's trace through a small example with string "ABCDEFG" and numRows = 3:

Initial Setup:

• g = [[], [], []] (three empty rows)
• i = 0 (starting at row 0)
• k = -1 (initial direction, will flip immediately)

Processing each character:

1. 'A' (index 0):

   • Add 'A' to g[0] → g = [['A'], [], []]
   • At row 0 (boundary), flip k = -(-1) = 1
   • Move to row: i = 0 + 1 = 1

2. 'B' (index 1):

   • Add 'B' to g[1] → g = [['A'], ['B'], []]
   • Not at boundary (row 1)
   • Move to row: i = 1 + 1 = 2

3. 'C' (index 2):

   • Add 'C' to g[2] → g = [['A'], ['B'], ['C']]
   • At row 2 (boundary, numRows-1), flip k = -(1) = -1
   • Move to row: i = 2 + (-1) = 1

4. 'D' (index 3):

   • Add 'D' to g[1] → g = [['A'], ['B', 'D'], ['C']]
   • Not at boundary (row 1)
   • Move to row: i = 1 + (-1) = 0

5. 'E' (index 4):

   • Add 'E' to g[0] → g = [['A', 'E'], ['B', 'D'], ['C']]
   • At row 0 (boundary), flip k = -(-1) = 1
   • Move to row: i = 0 + 1 = 1

6. 'F' (index 5):

   • Add 'F' to g[1] → g = [['A', 'E'], ['B', 'D', 'F'], ['C']]
   • Not at boundary (row 1)
   • Move to row: i = 1 + 1 = 2

7. 'G' (index 6):

   • Add 'G' to g[2] → g = [['A', 'E'], ['B', 'D', 'F'], ['C', 'G']]
   • At row 2 (boundary), flip k = -(1) = -1
   • (No more characters to process)

Visual Pattern:

Row 0: A   E
Row 1: B D F  
Row 2: C   G

Final Result: Joining all rows: "AE" + "BDF" + "CG" = "AEBDFCG"

The direction variable k acts like a bouncing ball - it changes from moving down (k=1) to moving up (k=-1) whenever we hit the top or bottom row, creating the zigzag pattern naturally.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through each character in the string s exactly once. For each character, it performs constant time operations:

• Appending to a list: O(1) amortized
• Checking conditions and updating variables i and k: O(1)

After the loop, ''.join(chain(*g)) operations take O(n) time since:

• chain(*g) creates an iterator over all elements: O(n)
• ''.join() concatenates all n characters: O(n)

Therefore, the overall time complexity is O(n) + O(n) = O(n), where n is the length of the string s.

Space Complexity: O(n)

The algorithm uses additional space for:

• The list g containing numRows sublists that collectively store all n characters from the input string: O(n)
• The output string created by ''.join(): O(n)
• A few variables (i, k): O(1)

The dominant factor is the storage of all characters, giving us a total space complexity of O(n), where n is the length of the string s.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Direction Change Timing

A common mistake is changing direction after moving to the next row instead of before. This causes characters to be placed in wrong rows.

Incorrect approach:

for char in s:
    rows[current_row].append(char)
    current_row += direction  # Moving first
    if current_row == 0 or current_row == numRows - 1:
        direction = -direction  # Then checking

This would cause index out of bounds errors or incorrect placement because you might move past valid row indices before checking.

Solution: Always check for boundary conditions and change direction BEFORE updating the row index.

2. Forgetting the Edge Case of numRows = 1

Without handling numRows = 1, the algorithm enters an infinite loop at the direction change condition since current_row is always both 0 and numRows - 1, causing the direction to flip every iteration while the row never changes.

Problem scenario:

# Without the edge case check
# When numRows = 1, current_row is always 0
# The condition (current_row == 0 or current_row == numRows - 1) is always true
# Direction keeps flipping but current_row stays at 0

Solution: Always handle the numRows = 1 case explicitly at the beginning of the function.

3. Using Wrong Initial Direction Value

Starting with direction = 1 instead of direction = -1 can work but requires careful handling of the first character.

Why it matters:

• With direction = -1: The first character triggers a direction change (since current_row = 0), setting direction = 1 to move downward.
• With direction = 1: You'd need additional logic to prevent immediately moving down before placing the first character.

Solution: Initialize direction = -1 to ensure the pattern starts correctly with the natural flow of checking boundaries before movement.

4. Inefficient String Concatenation

Using string concatenation in a loop is inefficient in Python:

Inefficient approach:

result = ""
for row in rows:
    for char in row:
        result += char  # String concatenation in loop - O(n²) complexity

Solution: Use ''.join() for efficient string building, which has O(n) complexity where n is the total length of the string.