Hello, coding enthusiasts! ðŸ‘‹ Today, we’re going to unravel another challenging problem from LeetCode: “Zigzag Conversion”.

## Problem Statement

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
```

And then read line by line: `"PAHNAPLSIIGYIR"`

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

`string convert(string s, int numRows);`

## Constraints

`1 <= s.length <= 1000`

`s`

consists of English letters (lower-case and upper-case), ‘,’ and ‘.’.`1 <= numRows <= 1000`

## Examples

**Example 1:**

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

**Example 2:**

```
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
```

**Example 3:**

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

## Analysis

Our task is to convert a given string into a zigzag pattern with a specified number of rows and then read the result line by line.

## Approach

The most efficient approach to solve this problem is to use a list of strings to represent each row of the zigzag pattern. Here’s how it works:

**Initialize a list of strings**: Create a list of strings`rows`

with a length equal to the minimum of`numRows`

and the length of`s`

.**Fill the rows**: Iterate over`s`

, adding each character to the correct row in`rows`

. Use a variable`curRow`

to keep track of the current row, and a variable`direction`

to keep track of whether we’re moving up or down the rows.**Join the rows**: Join the strings in`rows`

together to form the final result.

## Time Complexity

The time complexity for this approach is `O(n)`

, where `n`

is the length of the string. This is because we’re iterating over `s`

once.

## Space Complexity

The space complexity is also O(n), as we’re storing the result in a list of strings.

## Code

Here’s the Python and JavaScript code for this approach:

### Python

```
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
res = [''] * numRows
index, step = 0, 1
for char in s:
res[index] += char
if index == 0:
step = 1
elif index == numRows - 1:
step = -1
index += step
return ''.join(res)
```

### JavaScript

```
var convert = function(s, numRows) {
if (numRows == 1 || numRows >= s.length) {
return s;
}
let res = Array(numRows).fill('');
let index = 0, step = 1;
for (let char of s) {
res[index] += char;
if (index == 0) {
step = 1;
} else if (index == numRows - 1) {
step = -1;
}
index += step;
}
return res.join('');
};
```

## Conclusion

In this post, we tackled the “Zigzag Conversion” problem from LeetCode using a list of strings to represent the rows of the zigzag pattern. This solution has a time complexity of `O(n)`

and a space complexity of `O(n)`

.

Happy coding ðŸ˜„!

**Learn More:**

- LeetCode #5 – Longest Palindromic Substring
- LeetCode #4 â€“ Median of Two Sorted Arrays
- LeetCode #9 â€“ Palindrome Number
- LeetCode â€“ Longest Substring Without Repeating Characters
- LeetCode #2 â€“ Add Two Numbers
- LeetCode #1 â€“ Two Sum
- Asymptotic Notations: A Comprehensive Guide
- Big O Notation: A Simple Explanation With Examples
- Data Structure and Algorithm Tutorials