Zig-Zag Conversion

Moderate
0/80
profile
Contributed by
15 upvotes
Asked in companies
SquadstackFreshworksAmerican Express

Problem statement

You are given a string ‘S’ and an integer ‘ROW’, convert the row into a zig-zag pattern with rows equal to ‘ROW’ and output it row-wise. You may refer to the example below to better understand what the zig-zag pattern means.

Example : 
If ‘S’ = “beaninjacoder” and ‘ROW’ = 4

Then the zig-zag pattern is:
b         j        r
e     n   a     e
a   i     c   d
n         o

Therefore, we will print “bjrenaeaicdno”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a string ‘S’, denoting the input string.

The second line of each test case contains a single integer ‘ROW’, denoting the number of rows in the zig-zag pattern to be created.
Output Format : 
For each test case, print the new string after zig-zag conversion.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ ‘T’ ≤ 10      
1 ≤ |S| ≤ 10000
1 ≤ ‘ROW’ ≤ 10000
S only contains lower case English alphabets


Time limit: 1 sec
Sample Input 1 :
2
beaninjacoder
4
codingninjas
2
Sample Output 1 :
bjrenaeaicdno
cdnnnaoigijs
Explanation For Sample Input 1 :
For test case 1 :
We will print “bjrenaeaicdno” because the zig-zag pattern is:
b         j        r
e     n   a     e
a   i     c   d
n         o

And, we will now row-wise output the letters from this pattern formed.

For test case 2 : 
We will print “cdnnnaoigijs” because the zig-zag pattern is:
c  d  n  n  n  a     
o  i  g  i  j  s
Sample Input 2 :
2
canyousolvethisproblem
5
canyousolvethisproblem
3
Sample Output 2 :
clraovponsesbyutilmohe
colhreayuovtipolmnsesb
Hint

Look for a pattern in how the indices appear in a particular row.

Approaches (1)
Pattern Formation

Consider the case where the number of rows is equal to 10, and everything has a 0 based indexing. In that case, the input string's indexes form the given pattern:

Here Step-2 involves passing through the lower part of the zig-zag, and Step-1 involves passing the upper part of the zig-zag.

 

Using some pattern recognition we can find all the indices that lie in a particular row. Let’s say we need to find all the indices that lie in 5’th row, the first element will itself be the 5’th index and the next element can be calculated using the step-2, if curRow stores the current row number and curIdx stores the current index number then the next element will be after 2 * (|S| - 2 - curRow) + 2 indices. Further, we will apply the step-1 as we will now have to pass the upper part of the zig-zag and the next element will now lie after 2 * (curRow - 1) + 2 indices and to find the next element we will again have to apply the step-2 and the process we keep on repeating itself.

 

In general, we can find all the elements of each row and for a particular row, we can stop the search if the current index exceeds the length of the input string. But we need to cover the border case of the number of rows equal to one separately here, this is because of the way we have defined our pattern recognition formula above.

 

The steps are as follows :

  1. Check if ‘Row’ is equal to 1, then return the input string itself, this is the border case when the zig-zag conversion would have no effect on the original string.
  2. Initialize a variable ‘N’ equal to S.length, this variable stores the length of the input string.
  3. Declare a string ‘zigZag’, this string will store the final answer.
  4. Run a for loop for the variable ‘curRow’ from 0 to minimum of Row - 1 and N - 1, this is because that the number of rows will actually be used will be equal to ‘N’ if ‘N’ is less than ‘Row’, and we won’t have to handle any extra cases later on. Inside the loop:
    • Initialize a variable ‘curIdx’ equal to ‘curRow’, this variable will store the information about the current index.
    • Initialize a variable ‘step1’ equal to 2 * (curRow - 1) + 2.
    • Initialize a variable ‘step2’ equal to 2 * (N - 2 - curRow) + 2.
    • Insert the character at the curIdx’th index of the input string in the ‘zigZag’ string.
    • Run a while loop till the value of ‘curIdx’ is less than N’, inside the loop:
      • Check if ‘step2’ is greater than 0, then increment the ‘curIdx’ with step2’s value, and check if the new ‘curIdx’ is less than ‘N’ and then insert the character at the curIdx’th index of the input string in the ‘zigZag’ string.
      • Now check if ‘step1’ is greater than 0, then increment the ‘curIdx’ with step1’s value, and check if the new ‘curIdx’ is less than ‘N’ and then insert the character at the curIdx’th index of the input string in the ‘zigZag’ string.
  5. Finally, return the string ‘zigZag’.
Time Complexity

O( N ), where N denotes the length of the string.

 

While searching for indices lying in each row, each index of the input string is visited exactly once. The number of indices in the input string is equal to the length of the string.

Hence the time complexity is O( N ).

Space Complexity

O( N ), where N denotes the length of the string.

 

Extra space is used to store the string after zig-zag conversion, the length of this string is always equal to the length of the input string.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Zig-Zag Conversion
Full screen
Console