In this article, we have solved the problem of ZigZag Conversion of String with N rows. We take a string and a number N (rows) as input and distribute the string in ZigZag fashion among N rows and print the final string.

Table of contents

• Introduction to Problem Statement
• Method 1
• Method 2
• Time and Space Complexity
• Overview

This is similar to Leetcode Problem 6. ZigZag Conversion. Let us get started with ZigZag Conversion of String with N rows.

Introduction to Problem Statement

In this article, we will be discussing some techniques in string travesal. Say we have a string, along with n number of rows and we want to print this string in a zig-zag format, there are a number of methods we can use to concatenate the rows of the zig-zag and print the final string.

Example

Input: OPENGENUSISTHEBEST
Rows: 2

Then we covert the input string in a zig-zag format with the number of rows specified:

O  E  G  N  S  S  H  B  S
 P  N  E  U  I  T  E  E  T

Concatenating each row to a string will give us the following ouput:
OEGNSSHBSPNEUITEET

Method 1

The first approach we can take to this problem involves decomposing the string so that we deal with individual characters at a time. Since every character has to be placed in a particular row. We can use a set method to place each individual character in the correct row.

Traversal method:

• Append the current character to the string of the current row
• If the row number is n-1, direction equals up
• If the row number is 0, direction equals down
• If the direction is down, increment the row by 1, if it is not, decrement the row by 1

Using this process, we can ensure that each character is placed in the correct row in correspondence to the number of rows defined. We can then apply this within the general method as shown below.

Overall method

• Create an array of n strings
• Initialise row to 0, and create a direction variable, indicating whether the character needs to be placed above or below the current row
• Use traversal method described above
• Print the strings contained in our array

Python Code

Here is the implementation of the above method in Python:

def print_zigzag_concat(str, n):
    if n == 1:
        print(str)
        return
    
    l = len(str)
    arr=[""for x in range(l)]
    row = 0

    for i in range(l):
        arr[row] += str[i]
        if row == n-1:
            down = False
        elif row == 0:
            down = True
        
        if down:
            row += 1
        else:
            row -= 1

    for i in range(n):
        print(arr[i],end="")

print_zigzag_concat(str="OPENGENUS",n=3)

In this case, we input the string OPENGENUS and separate it into 3 rows. The output of our program is O.

Explanation

Input: OPENGENUS
Rows: 3

Zig-Zag string:
O    G     S
 P  N  E  U 
  E     N   
  
We then concactenate each row, leading to the output: OGSPNEUEN  

Method 2

We have so far covered how to solve this problem using arrays. Another method for solving this is through the use of imaginary matrices. This method calculates the place of each character as they are iterated through.

Matrix Properties

• For any full column, odd have n_row characters, even have n_row-2 characters
• You can read a single character from each expanded column for the first and last row
• For all other rows, we can read 2 characters, one from the top and the other from the bottom

From these properties we can deduce 2 things:

Traversal rules

• First and last row, the index will increment by i+=2⋅(n-1)
• For other rows, if we are traversing downwards, the index will increment by 2⋅n_row, for upwards, it will increment by i+=2⋅(n-n_row-1)

Python Code

def zigzag_concat(str, n):
    if (n <= 1):
        return str
    
    result = ""

    for n_row in range(n):
        i = n_row
        up = True

        while(i < len(str)):
            result += str[i]
        
            if (n_row == 0 or n_row == n-1):
                i += (2*n-2)
            else:
                if(up):
                    i+=(2*(n-n_row)-2)
                else:
                    i += n_row*2
                up ^= True

    return result

print(zigzag_concat(str="OPENGENUS",n=3))

As in the first example, our input is OPENGENUS with 3 zig-zag rows, leading to the same output of OGSPNEUEN.

Explanation

Input: OPENGENUS
Rows(n): 3

Matrix constructed:
O N N  
P G U 
E E S 

Step by Step breakdown:

Since we know that i = (n-1) * 2 from our rules defined earlier, i += (3-1) * 2 = 4.
This means that the first character is located at index 0(O), the second at index 4(G), the third at index 8(S). For the middle row, we know that upwards traversal is i+=2 * (n-n_row-1) and downwards is 2 * n_row, therefore for upwards i+=2 * (3-2-1) = 2 and down is 2 * 2 = 4. So the first character will be at index 0 from this row (P) then 2(N) then 4(E). For the final row, we know that for traversing upwards(since last character in middle row was the second E), i=2, therefore the first character of the final row is U since the index of E is 5, 5+2=7, and at index 7 is U. The same rules then apply as the first row, so iterating through the rest of the matrix, the next character will be at index 2 which is E (since there are 8 indices, when the index passes 8 we can loop back to 0) and finally at index 6 (N).

Leaving us with the final output: OGSPNEUEN

Time and Space Complexity

Method 1:

Time complexity: O(n)
Auxiliary Space: O(n)

Where n is the length of the string inputted

Method 2:

Time complexity: O(n)
Space complexity: O(1)

Where n is the length of the string inputted

Overview

In the article at OpenGenus, I have gone over a few ways to print concatenated n row strings in a zig-zag patten using both arrays and imaginary matrices with the time/space complexity for each approach and Python implementations to hopefully give you a nice introduction to some methods of string traversal and efficient ways to overcome this problem.