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

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Java

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 🙂

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Noogler
Guest
Noogler

I have a another code like this, can you solve this ?