Algorithm Day102 - Zigzag Conversion

🧩 Problem Description

LeetCode 6 - Zigzag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows, like this:

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

Then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows.

Example:

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

---

💡 First Thought (Simulation)

We can simulate the zigzag process by writing characters row by row.
Keep track of the current row and the direction (down or up).

---

⚙️ Optimized Approach — Row Buckets

We maintain a list of StringBuilder objects, one for each row,
and iterate over the string while changing direction when we hit the top or bottom row.

Java Code

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

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();

        int curRow = 0;
        boolean goingDown = false;

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

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

---

⏱️ Complexity Analysis

Operation	Time Complexity	Space Complexity
Iterate over string	O(n)	O(n)

---

🧠 Key Takeaways

• Zigzag pattern can be simulated by tracking row direction.
• Great example of string traversal with controlled direction change.
• Easy to visualize and implement with StringBuilder[].

---

📘 Next Step: We’ll look into string pattern transformation problems in the next post.