Published in

Geek Culture

# Introduction:

This post discusses the solution for zigzag string conversion in leetcode. Please note that there may be multiple solutions for this problem and the solution discussed here is just one among them. Any alternative or better solutions are welcome.

# Problem Statement:

Given a string, convert the string to zigzag format and print the output.

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

Example 1:

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

Example 2:

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

Example 3:

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

# Brainstorming:

We have been given a string of length n and number of rows to display the string. The idea here is not to print the string in the zigzag format, rather to print the output if it was written in the zigzag format.

For instance, the string `PAYPALISHIRING` has to be written as `PAHNAPLSIIGYIR`, the idealogy here is, the characters `PAHN` appear in row 1, `APLSIIG` appear in row 2 and `YIR` appear in row 3.

The moment we see this problem, we inherently think in the lines of printing the string character by character on consecutive rows. Trust me, that’s exactly what I was doing initially. However, if you read the problem statement carefully, all we need is to print the output like it is converted to zigzag format.

# Solution:

Let’s say the number of rows is 3, create a list with empty strings equal to the number of rows provided. The reason we create this list is, every row in the zigzag string corresponds to an index in this list.

Now, the first row should have the characters `PAHN`, which means they should be added to the first index of the list. Similarly, `APLSIIG` in index 2 and `YIR` in index 3 of the list respectively.Of course, we may not know the order of characters before we solve, unless we literally write the zigzag order on a paper.

All we have is the string and the number of rows.We should leverage the number of rows field to arrive at this solution.

# Output:

`['PAYPALISHIRING', '', '']`

Well!! well!! We have taken our baby steps in solving this. We have initialised a `line_no` variable to add characters from the string in corresponding indices.However, one pitfall here is all characters are being added to the first index. We need to split the characters and add them to different indices.

To do this, we need a variable to go back and forth between the indices. Basically traverse through the positive and negative indices. Now we will introduce a second variable to do this.

We have introduced a switcher variable that will traverse through the list. We multiply it with -1 as and when we hit the 0th index or the last index. To give a clearer picture, I have added print statements for each iteration. Let’s see the output now.

`['P', '', '']['P', 'A', '']['P', 'A', 'Y']['PP', 'A', 'Y']['PPA', 'A', 'Y']['PPAL', 'A', 'Y']['PPALI', 'A', 'Y']['PPALIS', 'A', 'Y']['PPALISH', 'A', 'Y']['PPALISHI', 'A', 'Y']['PPALISHIR', 'A', 'Y']['PPALISHIRI', 'A', 'Y']['PPALISHIRIN', 'A', 'Y']['PPALISHIRING', 'A', 'Y']['PPALISHIRING', 'A', 'Y']None`

Now, we still don’t have the desired output. However, based on the switcher variable, w e see that the characters get added to the corresponding index in the list.Finally, all we need to do is join the characters in the string and handle the corner case of rows < 1.

Below is the final and complete code.

# Output:

`PAHNAPLSIIGYIR`

If you wish to see the intermediate output, add print statements like we did in the previous code.

`['P', '', '']['P', 'A', '']['P', 'A', 'Y']['P', 'AP', 'Y']['PA', 'AP', 'Y']['PA', 'APL', 'Y']['PA', 'APL', 'YI']['PA', 'APLS', 'YI']['PAH', 'APLS', 'YI']['PAH', 'APLSI', 'YI']['PAH', 'APLSI', 'YIR']['PAH', 'APLSII', 'YIR']['PAHN', 'APLSII', 'YIR']['PAHN', 'APLSIIG', 'YIR']`

# Summary:

• The zigzag leetcode challenge is of difficulty medium.
• If you get an index error while solving in an interview, check if you are adding `line_no` with the `switcher` variable or whatever you call it and not with primitive 1. I've personally made this mistake.
• The time complexity of this solution is O(s) where s is the length of the string.

Please feel free to propose alternative solutions. All the very best.

Originally published at https://dock2learn.com on June 9, 2022.

--

--

## More from Geek Culture

A new tech publication by Start it up (https://medium.com/swlh).