Zigzag Conversion


Difficulty Level Medium
Frequently asked in PayPal
String

In the Zigzag Conversion problem, we have given a string s of length n and an integer r representing the number of rows. Convert the given string in the zigzag pattern of r rows and concatenate the characters row-wise. Print the new concatenated string.

Zigzag Conversion

Example

Input : 

s = “TutorialCup”

r = 3

Output : TrCuoilutap

Input : 

s = “Programming”

r = 4

Output : Pmramoriggn

Explanation for Zigzag Conversion

Let string s = “TutorialCup” and the number of rows i.e. r = 3

Initialize a string array a[ ] of size r to form the zigzag pattern. Also, initialize an integer variable row to track the current row as 0 and a boolean variable down.

Start traversing the string and update the string array as follows. Below are steps for the above example –

  • 1 : row = 0, down = true, a[ ] = T
  • 2 : row = 1, down = true, a[ ] = T, u
  • 3 : row = 2, down = false, a[ ] = T, u, t
  • 4 : row = 1, down = true, a[ ] = T, uo, t
  • 5 : row = 0, down = true, a[ ] = Tr, uo, t
  • 6 : row = 1, down = true, a[ ] = Tr, uoi, t
  • 7 : row = 2, down = false, a[ ] = Tr, uoi, ta
  • 8 : row = 1, down = true, a[ ] = Tr, uoil, ta
  • 9 : row = 0, down = true, a[ ] = TrC, uoil, ta
  • 10 : row = 1, down = true, a[ ] = TrC, uoilu, ta
  • 11 : row = 2, down = false, a[ ] = TrC, uoilu, tap

Therefore, the resulting string is TrCuoilutap

Algorithm for Zigzag Conversion

  1. Initialize a string s of length n and an integer r representing the number of rows.
  2. If the given number of rows(r) is 1 return string.
  3. Create an array of size r of string type.
  4. Initialize row as 0 and down of boolean type.
  5. Traverse from 0 to n-1 and store the characters of a string in string array at index row.
  6. Check if the row is equal to r-1 update down as false.
  7. Else if the row is 0 updates down as true.
  8. If down is true increment the row else decrement the row.
  9. Print the updated string array.

C++ Program for zigzag conversion

#include<bits/stdc++.h> 
using namespace std; 
  
void ZigZag(string s, int r){ 
    
    if(r == 1){ 
        cout<<s;       
        return; 
    }    
  
    int n = s.length(); 
  
    string a[r]; 
  
    int row = 0; 
    bool down; 
    
    for(int i=0; i<n; ++i){ 
        
        a[row].push_back(s[i]); 
  
        if(row == r-1) 
          down = false; 
  
        else if (row == 0) 
          down = true; 
  
        (down)? (row++): (row--); 
    } 
  
    for(int i=0; i<r; ++i) 
        cout<<a[i]; 
} 

int main(){ 
    string s = "TutorialCup"; 
    int r = 3; 
    ZigZag(s, r); 
    return 0; 
}
TrCuoilutap

Java Program for zigzag conversion

import java.util.Arrays; 
  
class Concatenate{ 
  
    static void ZigZag(String s, int r){ 
  
        if(r == 1){ 
            System.out.print(s); 
            return; 
        } 
        
        char[] str = s.toCharArray(); 
  
        int n = s.length(); 
  
        String[] a = new String[r]; 
        Arrays.fill(a, ""); 
  
        int row = 0; 
        boolean down = true;
        
        for(int i=0; i<n; ++i){ 
            
            a[row] += (str[i]); 
  
            if(row == r-1){ 
                down = false; 
            }  
              
            else if(row == 0){ 
                down = true; 
            } 
  
            if(down){ 
                row++; 
            }  
            else{ 
                row--; 
            } 
        } 
  
        for(int i=0; i<r; ++i){ 
            System.out.print(a[i]); 
        } 
    } 
  
    public static void main(String[] args){
        
        String s = "TutorialCup"; 
        int r = 3; 
        ZigZag(s, r);
        
    } 
}
TrCuoilutap

Complexity Analysis for Zigzag Conversion

Time Complexity: O(n) where n is the size of the input string.

Auxiliary Space: O(n) because we store the answer in an array(of type string) while computing the answer.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions