LeetCode 6 solution

Problem Statement (LeetCode 6 - Zigzag Conversion)

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this (example for numRows = 3):

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

Then, the output is read row by row:

"PAHNAPLSIIGYIR"

Write a function that converts a given string s into this zigzag pattern, then reads row-by-row.

Function Signature

string convert(string s, int numRows);

---

Example Input & Output

Example 1

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

Example 2

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

Explanation (numRows = 4):

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

Example 3

Input: s = "A", numRows = 1
Output: "A"

---

Optimal Approach: Using Row-wise Storage (O(n) Solution)

Intuition

1. The characters move diagonally down to fill rows, then move diagonally up.
2. We can simulate this movement using a list of strings.
3. We iterate once through the string (O(n)) and place characters in the correct row.

Steps to Solve

1. Create an array of strings (rows[numRows]) to store characters for each row.
2. Use a direction flag (down = true/false) to toggle between downward and upward movement.
3. Iterate through the input string and place characters into the correct row.
4. Concatenate all rows to get the final result.

Time & Space Complexity

• Time Complexity: O(n) (We traverse the string once).
• Space Complexity: O(n) (We store characters in row strings).

---

LeetCode-Compatible C++ Code

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;
        
        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;
        
        for (char c : s) {
            rows[currentRow] += c;
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }
        
        string result;
        for (string row : rows) {
            result += row;
        }
        
        return result;
    }
};

---

Step-by-Step Explanation

Simulation of Character Movement (numRows = 3)

Input: "PAYPALISHIRING"

Steps:

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

• Step 1: Add P to row 0, move down.
• Step 2: Add A to row 1, move down.
• Step 3: Add Y to row 2, move up.
• Step 4: Add P to row 1, move up.
• Step 5: Add A to row 0, move down.
• Step 6: Add L to row 1, move down.
• Repeat until all characters are placed.

Final row storage (3 rows)

rows[0] = "PAHN"
rows[1] = "APLSIIG"
rows[2] = "YIR"

Concatenating rows: "PAHNAPLSIIGYIR" ✅

---

Dry Run Example

Input: "PAYPALISHIRING", numRows = 4

Character Placement

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

Rows

rows[0] = "PIN"
rows[1] = "ALSIG"
rows[2] = "YAHR"
rows[3] = "PI"

Final Output: "PINALSIGYAHRPI"

---

Alternative Approaches & Why Not?

1️⃣ Brute Force (Simulate Entire Grid)

• Create a 2D character matrix of size numRows × length(s).
• Fill the matrix row by row, then read row-wise.
• ❌ Time Complexity: O(n²)
• ❌ Space Complexity: O(n²) (huge memory waste)

2️⃣ Using Indexing Formula

• Instead of maintaining a list, directly compute each character’s final position in the result.
• Hard to implement for numRows > 3.
• ❌ Too complex and difficult to maintain.

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Row-wise Storage (Best)	O(n)	O(n)	Simple & efficient
Brute Force (Grid Simulation)	O(n²)	O(n²)	Wasteful memory usage
Indexing Formula (Mathematical)	O(n)	O(1)	Hard to implement

---

Conclusion

• The row-wise storage approach is the best balance of simplicity and efficiency.
• Brute force is too slow, and indexing formulas are too complex.
• Time Complexity: O(n)
• Space Complexity: O(n)

---

Recommended Problems for Practice

1. Reverse Words in a String
2. Group Anagrams
3. Spiral Matrix

Master String Manipulation & Pattern Building to solve similar problems efficiently! 🚀