LeetCode 6: Zigzag Conversion – Python & JavaScript Solutions Explained

Zigzag Conversion - LeetCode Problem 6

Difficulty: Medium

Problem Statement

The string "PAYPALISHIRING" is written in a zigzag pattern with a given number of rows. The characters are then read row by row.

Example

    Input: s = "PAYPALISHIRING", numRows = 3
    Output: "PAHNAPLSIIGYIR"

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

Approach: Simulating Zigzag Rows (O(n) Complexity)

Instead of creating a 2D matrix, we store characters in different row lists and concatenate them.

Python Solution:

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

    rows = [""] * numRows
    index, step = 0, 1

    for char in s:
        rows[index] += char
        if index == 0:
            step = 1
        elif index == numRows - 1:
            step = -1
        index += step

    return "".join(rows)
    

JavaScript Solution:

function convert(s, numRows) {
    if (numRows === 1 || numRows >= s.length) return s;

    let rows = Array(numRows).fill("");
    let index = 0, step = 1;

    for (let char of s) {
        rows[index] += char;
        if (index === 0) step = 1;
        if (index === numRows - 1) step = -1;
        index += step;
    }

    return rows.join("");
}
    

Time Complexity Analysis

The algorithm runs in O(n) because we iterate through the string once and store characters in rows.

Conclusion

• Optimized row storage prevents unnecessary memory usage.
• O(n) time complexity makes it efficient for large inputs.