{"id":3108,"date":"2024-03-31T18:05:26","date_gmt":"2024-03-31T18:05:26","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=3108"},"modified":"2025-04-04T10:15:09","modified_gmt":"2025-04-04T10:15:09","slug":"zigzag-conversion-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/zigzag-conversion-problem\/","title":{"rendered":"Zigzag Conversion Problem (C++, Java, Python)"},"content":{"rendered":"\n

Pattern questions are complex; that’s why they are asked in lots of coding interviews. For example, create a triangle with the use of the \u2018*\u2019 symbol, print a string in a zigzag way, etc. All these types of questions need a basic understanding of any programming language. In this article, we will discuss the problem of \u201cZigzag Conversion\u201d.<\/p>\n\n\n\n

What is the Zigzag Conversion problem?<\/strong><\/h2>\n\n\n\n

In the ZigZag Conversion problem, you have been given a string that is written in a zigzag way with a given number of rows in it.<\/strong><\/p>\n\n\n\n

Brute Force: Using Array<\/strong><\/h3>\n\n\n\n

In this approach, we will create an array of size rows and push characters into the array according to their respective row number. Once we have stored all the characters in the array, we will iterate the array and create a string from it.<\/p>\n\n\n\n

Let\u2019s examine the approaches one by one:<\/p>\n\n\n\n

    \n
  1. First, create a vector of vector, of size = number of rows. It is used to store the characters of the string.<\/li>\n\n\n\n
  2. Now, create a Boolean variable flag that takes care of the direction in which we are moving, either upward or downward.<\/li>\n\n\n\n
  3. Create another variable j that takes care of the current row. <\/li>\n\n\n\n
  4. Now iterate over the string and check if we reached the 1st row or not. If it is the 1st row, change flag = false, which means we are now moving downward.<\/li>\n\n\n\n
  5. If we are at the last row, change flag = true which means we are now moving upward.<\/li>\n\n\n\n
  6. Store the character in the vector in their respective row. <\/li>\n\n\n\n
  7. At last, check if flag = true then decrease the j = j-1. Otherwise, increase j = j+1.<\/li>\n\n\n\n
  8. Now iterate over the vector row by row and store and append each row character into the resultant string.<\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above approach is O(n), where n is the size of the string. As we are iterating over the string once which takes O(n) time complexity. The space complexity is O(n) as we are storing each character of the string into a vector.<\/p>\n\n\n\n

    Optimized Approach<\/strong><\/h3>\n\n\n\n

    In the above approach, we are taking extra space. To reduce that extra space we will directly store that character in the resultant string instead of storing it first into the vector. This can be achieved with a simple observation. <\/p>\n\n\n\n

    All the characters that are present in the 1st and the last row will be (2*n)-2 distance apart from their neighboring characters. All the characters present other than these rows will repeat them after (2*(n-j) – 2) if we are moving downward and (2*j) if we are moving upward.<\/p>\n\n\n\n

    Let\u2019s examine this approach step by step.<\/p>\n\n\n\n

      \n
    1. Create a resultant string res. Now create a variable j which takes care of the current index.<\/li>\n\n\n\n
    2. Iterate over the rows and check if we are at the 1st or last row. Then, we update our current index with j = j + (2*n-2).<\/strong> Keep iterating till j < size of the string.<\/li>\n\n\n\n
    3. If we are at any other row, then update our current index with j = j + (2*(n-j)-2) if the flag is true. Otherwise, update the index with j = j + (2*j). <\/strong>Keep iterating till j < size of the string.<\/li>\n\n\n\n
    4. Keep adding the characters of the current index into the resultant string.<\/li>\n\n\n\n
    5. Return the resultant string at last.<\/li>\n<\/ol>\n\n\n\n

      Let\u2019s examine the code for the above approach.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Here is how you can implement the Optimized Approach in C++:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\n\nusing namespace std;\n\nstring zigzag_conversion(string s, int n){\n\n\u00a0\u00a0\u00a0\u00a0if(n <= 1) return s;\n\n\u00a0\u00a0\u00a0\u00a0string res = "";\n\n\u00a0\u00a0\u00a0\u00a0int j = 0, sz = s.size();\n\n\u00a0\u00a0\u00a0\u00a0for(int i=0;i<n;i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0bool flag\u00a0 = true;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j = i;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while(j<sz){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0res+= s[j];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(i == 0 || i == n-1){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2*n)-2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(flag){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2*(n-i))-2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}else{\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2*i);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0flag = !flag;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0return res;\n\n}\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0string s = "FAVTUTOR";\n\n\u00a0\u00a0\u00a0\u00a0int n = 4;\n\n\u00a0\u00a0\u00a0\u00a0string ans = zigzag_conversion(s, n);\n\n\u00a0\u00a0\u00a0\u00a0cout<<"Resultant string is: "<<ans<<endl;\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      Here is the same solution in Java:<\/p>\n\n\n\n
      class ZigzagConversion {\n\n\u00a0\u00a0\u00a0\u00a0public static String zigzagConversion(String s, int n) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (n <= 1) return s;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0StringBuilder res = new StringBuilder();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int j = 0, sz = s.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 0; i < n; i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0boolean flag = true;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j = i;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while (j < sz) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0res.append(s.charAt(j));\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (i == 0 || i == n - 1) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2 * n) - 2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (flag) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2 * (n - i)) - 2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2 * i);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0flag = !flag;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return res.toString();\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String s = "FAVTUTOR";\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int n = 4;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String ans = zigzagConversion(s, n);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println("Resultant string is: " + ans);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      You can implement in Python also:<\/p>\n\n\n\n
      def zigzag_conversion(s, n):\n\n\u00a0\u00a0\u00a0\u00a0if n <= 1:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return s\n\n\u00a0\u00a0\u00a0\u00a0res = ""\n\n\u00a0\u00a0\u00a0\u00a0j = 0\n\n\u00a0\u00a0\u00a0\u00a0sz = len(s)\n\n\u00a0\u00a0\u00a0\u00a0for i in range(n):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0flag = True\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j = i\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while j < sz:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0res += s[j]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if i == 0 or i == n - 1:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2 * n) - 2\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if flag:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += (2 * (n - i)) - 2\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0j += 2 * i\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0flag = not flag\n\n\u00a0\u00a0\u00a0\u00a0return res\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0s = "FAVTUTOR"\n\n\u00a0\u00a0\u00a0\u00a0n = 4\n\n\u00a0\u00a0\u00a0\u00a0ans = zigzag_conversion(s, n)\n\n\u00a0\u00a0\u00a0\u00a0print("Resultant string is:", ans)<\/pre><\/div>\n\n\n\n
      Output:<\/strong><\/p>\n\n\n\n
      Resultant srting is: FOATRVUT<\/code><\/pre>\n\n\n\n
      The time complexity for the above code is O(n) as we are just iterating the string once, which takes O(n) time complexity. The space complexity is O(1) as we are not using any extra space because we are directly storing the characters into the resultant string.<\/p>\n\n\n\n
      Here’s the difference between both approaches:<\/p>\n\n\n\n
      Analysis<\/strong><\/th>Time Complexity<\/strong><\/th>Space Complexity<\/strong><\/th>Description<\/strong><\/th><\/tr><\/thead>
      Brute Force<\/td>O(n)<\/td>O(n)<\/td>We are using extra space to first store the characters in their respective rows. Then, using those rows, we will create a string.<\/td><\/tr>
      Optimized<\/td>O(n)<\/td>O(1)<\/td>We are storing the values directly into the resultant string.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this article, we see various ways to solve the \u201cZigzag Conversion<\/a>\u201d problem. We had seen that we can store the characters in their respective rows and then for the resultant string from them. But we are using extra space to store the characters, which can be reduced if we iterate the string row-wise instead of column-wise. There are some more questions on patterns like \u201cLongest Palindromic Substring<\/a>,\u201d \u201cValid Parentheses<\/a>,\u201d etc. Try to solve these questions on your own to clear your fundamentals.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Pattern questions are complex; that’s why they are asked in lots of coding interviews. For example, create a triangle with the use of the \u2018*\u2019 symbol, print a string in a zigzag way, etc. All these types of questions need a basic understanding of any programming language. In this article, we will discuss the problem […]<\/p>\n","protected":false},"author":14,"featured_media":3112,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-3108","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=3108"}],"version-history":[{"count":5,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3108\/revisions"}],"predecessor-version":[{"id":7375,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3108\/revisions\/7375"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/3112"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=3108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=3108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=3108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}