Print string in zig-zag form in k rows

Given a string and a integer k, print the string in zig-zag form in k rows.

 

For example,

zig-zag-3-rows


zig-zag-4-rows


 

The idea is to identify a pattern in the problem. If we consider a character’s index in the output, we have observed some patterns –

  • First key of each row i is present at index i in the string.
     
  • For the first and the last row, the distance between each key is (k-1)*2. For example for k = 4, the difference is 6. So the first element of the first row is located at index 0, the second element is located at index 6, the third element at 12 and so on.. Similarly the first element of the last row is located at index 3, the second element is located at index 9, the third element at 15 and so on..
     
  • Now for all middle rows, depending upon we are going up or we are going down the index differs as evident from below code.
     

  zig-zag-4-rows-index

 
C++ implementation –
 

Download   Run Code

Output:

TOSMHRBIAOEIPLMWSSEE

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂