LeetCode 6: Zigzag Conversion

Problem Statement

LeetCode 6, Zigzag Conversion, is a medium-level challenge where you rearrange a string s into a zigzag pattern with a given number of rows, numRows, and then read it off row by row to form a new string. Imagine writing the string on a zigzag path down and up across the rows, then collecting the characters from each row left to right. The goal is to return the final string after this process.

Constraints

  • 1 <= s.length <= 1000: The string length is between 1 and 1000.
  • s consists of English letters (lowercase or uppercase), commas, and periods.
  • 1 <= numRows <= 1000: Number of rows is at least 1, up to 1000.

Example

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Explanation: Zigzag pattern:
P   A   H   N
A P L S I I G
Y   I   R
Read row by row: "PAHNAPLSIIGYIR".

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation: Zigzag pattern:
P     I    N
A   L S  I G
Y A   H R
P     I
Read row by row: "PINALSIGYAHRPI".

Input: s = "A", numRows = 1
Output: "A"
Explanation: With 1 row, it’s just "A".

Understanding the Problem

Picture writing a string like "PAYPALISHIRING" in a zigzag shape across a set number of rows. For 3 rows, you go down (P, A, Y), then diagonally up (A, P), down again (L, S), and so on. Then, read each row straight across: top row, middle row, bottom row. The result is a new string. If numRows is 1, it’s the original string unchanged. We’ll focus on:

  • Row-by-Row Construction: Build each row as we go through the string.

Solution: Row-by-Row Construction

Explanation

This method mimics the zigzag process by figuring out which row each character belongs to as we move through the string. We use a list to collect characters for each row, then join them at the end.

  1. Handle Base Case.
  • If numRows is 1, return the string as is—no zigzag needed.

2. Initialize Rows.

  • Create a list of empty strings, one for each row.

3. Assign Characters.

  • Move through the string, placing each character in its row based on the zigzag pattern (down, then up).
  • Use a row index and direction to track where we are.

4. Combine Rows.

  • Join all row strings into one final string.

Step-by-Step Example

Example 1: s = "PAYPALISHIRING", numRows = 3

We have the string "PAYPALISHIRING" and want to arrange it in a 3-row zigzag, then read it off.

  • Goal: Build the zigzag pattern and get the row-by-row string.
  • Result for reference: Pattern is:

P A H N A P L S I I G Y I R Reading rows gives "PAHNAPLSIIGYIR".

  • Start: Check rows—3 is more than 1, so proceed. Make 3 empty rows: ["", "", ""].
  • Step 1: Place "P" (position 0).
    • Start at row 0, going down. Add "P" to row 0.
    • Rows: ["P", "", ""], move to row 1.
  • Step 2: Place "A" (position 1).
    • Row 1, add "A".
    • Rows: ["P", "A", ""], move to row 2.
  • Step 3: Place "Y" (position 2).
    • Row 2, add "Y". Hit bottom, switch to going up.
    • Rows: ["P", "A", "Y"], move to row 1.
  • Step 4: Place "P" (position 3).
    • Row 1, add "P".
    • Rows: ["P", "AP", "Y"], move to row 0.
  • Step 5: Place "A" (position 4).
    • Row 0, add "A".
    • Rows: ["PA", "AP", "Y"], switch to down, move to row 1.
  • Step 6: Place "L" (position 5).
    • Row 1, add "L".
    • Rows: ["PA", "APL", "Y"], move to row 2.
  • Step 7: Place "I" (position 6).
    • Row 2, add "I".
    • Rows: ["PA", "APL", "YI"], switch to up, move to row 1.
  • Step 8: Place "S" (position 7).
    • Row 1, add "S".
    • Rows: ["PA", "APLS", "YI"], move to row 0.
  • Step 9: Place "H" (position 8).
    • Row 0, add "H".
    • Rows: ["PAH", "APLS", "YI"], switch to down, move to row 1.
  • Step 10: Place "I" (position 9).
    • Row 1, add "I".
    • Rows: ["PAH", "APLSI", "YI"], move to row 2.
  • Step 11: Place "R" (position 10).
    • Row 2, add "R".
    • Rows: ["PAH", "APLSI", "YIR"], switch to up, move to row 1.
  • Step 12: Place "I" (position 11).
    • Row 1, add "I".
    • Rows: ["PAH", "APLSII", "YIR"], move to row 0.
  • Step 13: Place "N" (position 12).
    • Row 0, add "N".
    • Rows: ["PAHN", "APLSII", "YIR"], switch to down, move to row 1.
  • Step 14: Place "G" (position 13).
    • Row 1, add "G".
    • Rows: ["PAHN", "APLSIIG", "YIR"], move to row 2 (but string ends).
  • Finish: Combine rows: "PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR".
    • Matches the zigzag pattern read row by row.

Example 2: s = "PAYPALISHIRING", numRows = 4

Same string, but with 4 rows.

  • Goal: Arrange in a 4-row zigzag and read it off.
  • Result for reference: Pattern is:

P I N A L S I G Y A H R P I Reading rows gives "PINALSIGYAHRPI".

  • Start: 4 rows, so make ["", "", "", ""].
  • Step 1: "P" to row 0.
    • Rows: ["P", "", "", ""], row 1.
  • Step 2: "A" to row 1.
    • Rows: ["P", "A", "", ""], row 2.
  • Step 3: "Y" to row 2.
    • Rows: ["P", "A", "Y", ""], row 3.
  • Step 4: "P" to row 3.
    • Rows: ["P", "A", "Y", "P"], switch to up, row 2.
  • Step 5: "A" to row 2.
    • Rows: ["P", "A", "YA", "P"], row 1.
  • Step 6: "L" to row 1.
    • Rows: ["P", "AL", "YA", "P"], row 0.
  • Step 7: "I" to row 0.
    • Rows: ["PI", "AL", "YA", "P"], switch to down, row 1.
  • Step 8: "S" to row 1.
    • Rows: ["PI", "ALS", "YA", "P"], row 2.
  • Step 9: "H" to row 2.
    • Rows: ["PI", "ALS", "YAH", "P"], row 3.
  • Step 10: "I" to row 3.
    • Rows: ["PI", "ALS", "YAH", "PI"], switch to up, row 2.
  • Step 11: "R" to row 2.
    • Rows: ["PI", "ALS", "YAHR", "PI"], row 1.
  • Step 12: "I" to row 1.
    • Rows: ["PI", "ALSI", "YAHR", "PI"], row 0.
  • Step 13: "N" to row 0.
    • Rows: ["PIN", "ALSI", "YAHR", "PI"], switch to down, row 1.
  • Step 14: "G" to row 1.
    • Rows: ["PIN", "ALSIG", "YAHR", "PI"], row 2 (string ends).
  • Finish: Combine: "PIN" + "ALSIG" + "YAHR" + "PI" = "PINALSIGYAHRPI".
    • Matches the 4-row zigzag.

Code

def convert(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s

    rows = [""] * numRows
    current_row = 0
    step = 1  # 1 for down, -1 for up

    for char in s:
        rows[current_row] += char
        if current_row == 0:
            step = 1  # Hit top, go down
        elif current_row == numRows - 1:
            step = -1  # Hit bottom, go up
        current_row += step

    return "".join(rows)

Complexity

  • Time Complexity: O(n) – One pass through the string.
  • Space Complexity: O(n) – Space for the rows (total characters).

Efficiency Notes

This is fast and efficient, using minimal extra space beyond the output, making it the go-to solution.

Alternative: Mathematical Indexing (Brief Mention)

Explanation

You could calculate the exact index of each character in the final string using the zigzag cycle (2 * numRows - 2), but it’s trickier and less intuitive than building rows directly, so we stick with the row-by-row method.

Additional Example

For s = "ABCDE", numRows = 3:

  • Goal: Zigzag with 3 rows.
  • Reference:

A C E B D Result: "ACEBD".

  • Steps:
    • "A" to row 0, "B" to row 1, "C" to row 0, "D" to row 1, "E" to row 0.
    • Rows: ["ACE", "BD", ""], combine: "ACEBD".

Edge Cases

  • One Row: s = "ABC", numRows = 1 – Returns "ABC".
  • String Fits Rows: s = "AB", numRows = 3 – Returns "AB".
  • Single Character: s = "A", numRows = 2 – Returns "A".

Final Thoughts

  • Row-by-Row: Simple, fast, and intuitive, perfect for this problem.
  • Practice Value: Teaches pattern recognition and string manipulation.