Print given String in ZigZag Fashion

Problem Definition

Given a string and a number of lines $k$, print the string in zigzag form.

In zigzag, characters are printed out diagonally from top left to bottom right until reaching the $kth$ line, then back up to top right, and so on.

For example, given the sentence "thisisazigzag" and k = 4, you should print:

t     a     g
 h   s z   a
  i i   i z
   s     g

Solution

The solution to this problem would be to construct $k$ lines and print them.

Key Problem

Construction of each of the line is the key part of this problem. Each line would consist necessary characters from the $input\ string$ separated by required number of $spaces$. To construct each line we need to identify characters belonging to the line and number of spaces to be inserted after/before each of the characters.

Basic Algorithm

To construct each line,

1. Insert necessary number of spaces in the beginning of the line
2. Identify next character that belongs to this line and append to it
3. Append necessary number of spaces
4. Go to step 2, if there are more characters that belong to this line, otherwise print the line and move on to next line

Identify Size of spaces and Next Belonging Character

Assuming $0\ index$ based line numbers.

1. For $ith\ line$, number of spaces that starts the line $=\ i$
2. Index (say $index$) of first character that belong to $ith\ line = i$
3. Number of spaces that follows after a character depends upon whether we are moving $up\ or\ down$. For simplicity we can assume that at character on first line $i = 0$, we are always moving $down$, while for the last line $i = k-1$, we are always moving $up$. For other lines we will be alternatively moving $up$ and $down$ starting from moving down because initially we are moving down.

             If we are moving up,
                gapSize = 2 * i - 1
   
             Else if we are moving down,
                j = k - i - 1
                gapSize = 2 * j - 1
           

   
4. Index of next character will be $index = index + gapSize + 1$

Implementation

Following is the implementation as described above.

Complexity

Ignoring the time complexity to construct string of empty spaces, the time complexity of this implementation is $O(n)$ because we go through each of the characters in the input string only once.

---

---

---