Zigzag Conversion - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Convert a string into a zigzag pattern with a given number of rows and read it off row by row to form a new string.
Handle the edge case: If numRows is 1, return the original string as no zigzag is needed.
Initialize a list of lists (rows) with numRows empty lists to store characters in each row.
Initialize variables: i (current row index) to 0 and d (direction) to 1 (moving down).
Iterate through each character in the string, appending it to the list at rows[i].
Update the row index: If i is 0, set d to 1 (move down); if i is numRows-1, set d to -1 (move up). Increment i by d.
Convert each row list into a string by joining its characters.
Join all row strings into a single string and return it.

Code Solution

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        i, d = 0, 1
        rows = [[] for _ in range(numRows)]

        for char in s:
            rows[i].append(char)
            if i == 0:
                d = 1
            elif i == numRows - 1:
                d = -1
            i += d

        for i in range(numRows):
            rows[i] = ''.join(rows[i])

        return ''.join(rows)
        # Time: O(n * numRows)
        # Space: O(n)

#include <string>
#include <vector>

class Solution {
public:
    std::string convert(const std::string& s, int numRows) {
        if (numRows == 1) return s;

        std::vector<std::string> rows(std::min(numRows, int(s.length())));
        int i = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[i] += c;
            if (i == 0 || i == numRows - 1) goingDown = !goingDown;
            i += goingDown ? 1 : -1;
        }

        std::string result;
        for (const std::string& row : rows) {
            result += row;
        }
        return result;
    }
};

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++) {
            rows.add(new StringBuilder());
        }

        int i = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) goingDown = !goingDown;
            i += goingDown ? 1 : -1;
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        return result.toString();
    }
}

var convert = function(s, numRows) {
    if (numRows === 1) return s;

    let rows = Array.from({ length: Math.min(numRows, s.length) }, () => []);
    let i = 0;
    let goingDown = false;

    for (let char of s) {
        rows[i].push(char);
        if (i === 0 || i === numRows - 1) goingDown = !goingDown;
        i += goingDown ? 1 : -1;
    }

    return rows.flat().join('');
};

Detailed Explanation

Understanding the Zigzag Conversion Problem

The Zigzag Conversion problem asks you to format a given string into a zigzag pattern across a specified number of rows, and then read the characters row-by-row to form the final output string. For example, if the input string is "PAYPALISHIRING" and the number of rows is 3, the zigzag pattern would visually look like this:

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

Reading the characters line by line produces the output: "PAHNAPLSIIGYIR".

When to Use Zigzag Formatting

This problem appears frequently in coding interviews because it tests string manipulation, control flow, and indexing logic. It's particularly useful for showcasing how you handle direction changes and how you organize character placement when working with visual patterns.

Optimal Strategy to Build the Zigzag Pattern

The most efficient way to solve this problem is to simulate the zigzag traversal by maintaining a list of strings—one for each row. As you iterate over the input string character by character, append each character to the appropriate row and change the direction of traversal when you reach the top or bottom row.

Begin by initializing a list with numRows empty strings. Then, use two variables: one for tracking the current row and one for determining the direction of traversal (down or up). If you're on the first row, start moving downward; if you're on the last row, reverse direction and begin moving upward. For every character in the input string, add it to the corresponding row, update the current row based on the direction, and continue this process until you've placed every character.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string. Each character is processed exactly once.
Space Complexity: O(n), since we're storing each character in one of the row lists before combining them.

Why This Problem Is Important

Zigzag Conversion is a great exercise in simulating state-based traversal and implementing a visual pattern with indexing logic. It’s also a problem that highlights your ability to recognize when extra structure (like direction flags or row containers) is needed to control data flow.

Conclusion

By using a simple row tracking mechanism and toggling direction when needed, this problem can be solved efficiently and elegantly. Understanding this approach lays the foundation for more advanced pattern-based string manipulation problems that you may encounter in technical interviews.

Get Personalized Support at AlgoMap Bootcamp 💡