{"id":3900,"date":"2023-06-23T18:07:41","date_gmt":"2023-06-23T12:37:41","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3900"},"modified":"2023-06-23T18:07:43","modified_gmt":"2023-06-23T12:37:43","slug":"spiral-order-matrix","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/spiral-order-matrix\/","title":{"rendered":"Spiral Order Matrix"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-iterative\">Approach 1: Iterative<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-recursive-solution\">Approach 2: Recursive Solution<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions:<\/a><\/li><li><a href=\"#faq\">FAQ<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-time-and-space-complexity-of-the-recursive-approach\">Q.1: What is the time and space complexity of the recursive approach?<\/a><\/li><li><a href=\"#q2-how-to-traverse-the-matrix-in-an-anti-clockwise-direction\">Q.2: How to traverse the matrix in an anti-clockwise direction?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a matrix <strong>A <\/strong>of size <strong>N X M<\/strong>. The task is to print the matrix in spiral order.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"596\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"spiral order\"  class=\"wp-image-4013 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 596px) 100vw, 596px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/spiral-order.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/spiral-order.png 596w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/spiral-order-300x252.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/spiral-order-380x319.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/spiral-order-550x461.png 550w\" ><\/figure>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: A[] <\/strong>= [[1, 2, 3, 4],<\/p>\n\n\n\n<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[5, 6, 7, 8],<\/p>\n\n\n\n<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[9, 10, 11, 12],<\/p>\n\n\n\n<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[13, 14, 15, 16]]<br><br><strong>Output:<\/strong> [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11 10]<br><strong>Explanation: <\/strong>Shown in image<\/p>\n\n\n\n<h2 id=\"approach-1-iterative\">Approach 1: Iterative<\/h2>\n\n\n\n<p>The idea is to traverse the given matrix in the following manner:<\/p>\n\n\n\n<ul><li>Traverse left to right.<\/li><li>Traverse top to bottom.<\/li><li>Traverse right to left<\/li><li>Traverse bottom to top<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"867\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Iterative\"  class=\"wp-image-4015 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Iterative.gif\" ><\/figure>\n\n\n\n<p>Continue these steps till all the elements have been visited.<\/p>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void spiralPrint(int m, int n, int a[R][C]) {\n  int i, k = 0, l = 0;\n \n  while (k &amp;lt; m &amp;amp;&amp;amp; l &amp;lt; n) {\n    for (i = l; i &amp;lt; n; ++i) {\n      cout &amp;lt;&amp;lt; a[k][i] &amp;lt;&amp;lt; \" \";\n    }\n    k++;\n    for (i = k; i &amp;lt; m; ++i) {\n      cout &amp;lt;&amp;lt; a[i][n - 1] &amp;lt;&amp;lt; \" \";\n    }\n    n--;\n    if (k &amp;lt; m) {\n      for (i = n - 1; i &amp;gt;= l; --i) {\n        cout &amp;lt;&amp;lt; a[m - 1][i] &amp;lt;&amp;lt; \" \";\n      }\n      m--;\n    }\n    if (l &amp;lt; n) {\n      for (i = m - 1; i &amp;gt;= k; --i) {\n        cout &amp;lt;&amp;lt; a[i][l] &amp;lt;&amp;lt; \" \";\n      }\n      l++;\n    }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static void spiralPrint(int m, int n, int a[][]) {\n  int i, k = 0, l = 0;\n \n  while (k &amp;lt; m &amp;amp;&amp;amp; l &amp;lt; n) {\n    for (i = l; i &amp;lt; n; ++i) {\n      System.out.print(a[k][i] + \" \");\n    }\n    k++;\n    for (i = k; i &amp;lt; m; ++i) {\n      System.out.print(a[i][n - 1] + \" \");\n    }\n    n--;\n    if (k &amp;lt; m) {\n      for (i = n - 1; i &amp;gt;= l; --i) {\n        System.out.print(a[m - 1][i] + \" \");\n      }\n      m--;\n    }\n    if (l &amp;lt; n) {\n      for (i = m - 1; i &amp;gt;= k; --i) {\n        System.out.print(a[i][l] + \" \");\n      }\n      l++;\n    }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def spiralPrint(m, n, a):\n    k = 0\n    l = 0\n \n    while k &amp;lt; m and l &amp;lt; n:\n        for i in range(l, n):\n            print(a[k][i], end=\" \")\n \n        k += 1\n        for i in range(k, m):\n            print(a[i][n - 1], end=\" \")\n \n        n -= 1\n        if k &amp;lt; m:\n \n            for i in range(n - 1, (l - 1), -1):\n                print(a[m - 1][i], end=\" \")\n \n            m -= 1\n \n        if l &amp;lt; n:\n            for i in range(m - 1, k - 1, -1):\n                print(a[i][l], end=\" \")\n \n            l += 1<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N * M), where N * M is the total size of the matrix<\/li><li><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/li><\/ul>\n\n\n\n<h2 id=\"approach-2-recursive-solution\">Approach 2: Recursive Solution<\/h2>\n\n\n\n<p>Similar to the last approach, we can try to solve this problem recursively. The idea of this approach is exactly similar to the iterative approach.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Consider four variables, i.e. <strong>starting_row, ending_row, starting_col, ending_col<\/strong>.<\/li><li>Create a recursive function for printing the spiral matrix.<\/li><li>Base cases would be: If the starting index of row\/col is less than the size of <strong>row\/col<\/strong>, then, terminate the function, else continue printing the boundary elements.<\/li><li>Run a loop from left to right and print the element.<\/li><li>Similarly, run a loop from top to bottom and right to left, and bottom to top.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void print(int arr[R][C], int i, int j, int m, int n) {\n  if (i &amp;gt;= m or j &amp;gt;= n)\n    return;\n \n  for (int p = j; p &amp;lt; n; p++)\n    cout &amp;lt;&amp;lt; arr[i][p] &amp;lt;&amp;lt; \" \";\n \n  for (int p = i + 1; p &amp;lt; m; p++)\n    cout &amp;lt;&amp;lt; arr[p][n - 1] &amp;lt;&amp;lt; \" \";\n \n  if ((m - 1) != i)\n    for (int p = n - 2; p &amp;gt;= j; p--)\n      cout &amp;lt;&amp;lt; arr[m - 1][p] &amp;lt;&amp;lt; \" \";\n \n  if ((n - 1) != j)\n    for (int p = m - 2; p &amp;gt; i; p--)\n      cout &amp;lt;&amp;lt; arr[p][j] &amp;lt;&amp;lt; \" \";\n \n  print(arr, i + 1, j + 1, m - 1, n - 1);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static void print(int arr[][], int i, int j, int m,\n    int n) {\n    if (i &amp;gt;= m || j &amp;gt;= n) {\n      return;\n    }\n \n    for (int p = i; p &amp;lt; n; p++) {\n      System.out.print(arr[i][p] + \" \");\n    }\n \n    for (int p = i + 1; p &amp;lt; m; p++) {\n      System.out.print(arr[p][n - 1] + \" \");\n    }\n    if ((m - 1) != i) {\n      for (int p = n - 2; p &amp;gt;= j; p--) {\n        System.out.print(arr[m - 1][p] + \" \");\n      }\n    }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def printdata(arr, i, j, m, n):\n    if i &amp;gt;= m or j &amp;gt;= n:\n        return\n \n    for p in range(i, n):\n        print(arr[i][p], end=\" \")\n \n    for p in range(i + 1, m):\n        print(arr[p][n - 1], end=\" \")\n \n    if (m - 1) != i:\n        for p in range(n - 2, j - 1, -1):\n            print(arr[m - 1][p], end=\" \")\n \n    if (n - 1) != j:\n        for p in range(m - 2, i, -1):\n            print(arr[p][j], end=\" \")\n \n    printdata(arr, i + 1, j + 1, m - 1, n - 1)<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N * M), where N * M is the total size of the matrix<\/li><li><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/li><\/ul>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions:<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/spiral-order-matrix-i\/\" target=\"_blank\" rel=\"noreferrer noopener\">Spiral Order Matrix I<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-time-and-space-complexity-of-the-recursive-approach\"><span id=\"q-1-what-is-the-time-and-space-complexity-of-the-recursive-approach\">Q.1: What is the time and space complexity of the recursive approach?<\/span><\/h3>\n\n\n\n<p>Ans: The time and space complexity of the recursive approach is O(N * M) and O(1).<\/p>\n\n\n\n<h3 id=\"q2-how-to-traverse-the-matrix-in-an-anti-clockwise-direction\"><span id=\"q-2-how-to-traverse-the-matrix-in-an-anti-clockwise-direction\">Q.2: How to traverse the matrix in an anti-clockwise direction?<\/span><\/h3>\n\n\n\n<p>Ans: The idea is the same. Just traverse the matrix from top to down, left to right, bottom to top and right to left.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a matrix A of size N X M. The task is to print the matrix&hellip;\n","protected":false},"author":5,"featured_media":4016,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[582],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3900"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3900"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3900\/revisions"}],"predecessor-version":[{"id":20710,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3900\/revisions\/20710"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4016"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3900"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3900"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3900"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}