Tutorials on Advanced Math and Computer Science Concepts

Problem 6 - Zigzag Convestion (Medium)

Code for this problem can be found at: https://github.com/scprogramming/LeetcodeExplained/tree/master/Problem%206%20-%20ZigZag%20Conversion%20(Medium)

Problem: Given a string of text, write the text in a zig zag pattern, with the given number of rows

To best understand this problem, it is important to look at some examples to see what exactly is being asked.

If our input for instance was: "paypalishiring", and our row count was 3, we would write the output as follows:

P    A   H   N


Y     I    R

What this is basically doing is alternating where the letter is being placed. You can see that the first letter is placed in the first row, then the second letter skips an index, and writes to the next available one. This pattern repeats for the first row, until we reach the second row. One the second row, we write in the rows that have been written, as well as the rows that have spaces. Then we return to the original pattern for the third row.

This gives you an idea of what we want to happen. We want to write out the text such that it creates a zig zag pattern as shown. The actual output of the program is the string concatenated in each line. So since the first line is PAHN and the next line is APLSIIG, we get an output PAHNAPLSIIGYIR

So, how exactly can we program something like this? There are several different solutions we can use, and I'll be demonstrating one here that runs O(n) time complexity, where n is the length of the string.

First off, if the number of rows is 0 or 1, we can just return the provided string, since nothing has to be done with it. Next, we are going to write each row, row by row, which will give us the full write of all the rows with one pass on the string. This can be done using the following code:

We start with the first row. At the first row, we will immediately place the value at (numRows + numRows - 2). Once this is done, we iterate the string placing the value on even iterations and moving passed it on odd number iterations. You can see that in every case, we need to iterate the string for each character, examining for odd and even indexes, and placing as required. This is since the zig zag pattern will either skip or place a letter based on what is currently present.

Analyzing the time complexity of this algorithm, we can see that we iterate the string once for each row that exists. This would give us a time efficiency of O(c*n), where c is a constant value representing the row number, and n is the size of the string. This in general will trend to O(n) complexity, since the number of rows will be small enough to be neglected.