{"id":3604,"date":"2021-11-11T18:03:00","date_gmt":"2021-11-11T12:33:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3604"},"modified":"2021-11-11T18:03:01","modified_gmt":"2021-11-11T12:33:01","slug":"maximum-sum-rectangle","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/maximum-sum-rectangle\/","title":{"rendered":"Maximum Sum Rectangle"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><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=\"#-sample-test-cases--\"><strong>Sample Test Cases :<\/strong><\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#optimal-approach\">Optimal Approach<\/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><li><a href=\"#practice-problem\">Practice Problem<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a 2D matrix, find the largest possible sum submatrix in it and print its value.<\/p>\n\n\n\n<p><strong>Submatrix<\/strong>: In this problem, a submatrix is defined as a rectangle, which can be obtained by deleting a certain number of boundary rows and columns from the given original matrix. All elements of the rectangle need to be <strong>contiguous<\/strong> either row-wise or column-wise.<\/p>\n\n\n\n<h2 id=\"-sample-test-cases--\"><span id=\"sample-test-cases\"><strong>Sample Test Cases :<\/strong><\/span><\/h2>\n\n\n\n<p><strong>Input 1:<\/strong><br><strong>Matrix <\/strong>=<br>{{1, 2, -1, -4, -20},<br>{-8, -3, 4, 2, 1},<br>{3, 8, 10, 1, 3},<br>{-4, -1, 1, 7, -6}}<\/p>\n\n\n\n<p><strong>Output 1:<\/strong><br>(top, left) : (1, 1)<br>(bottom, right) : (3, 3)<br>29<br><strong>Explanation 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"622\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3665 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-1024x622.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-1024x622.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-300x182.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-768x467.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-380x231.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-550x334.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-800x486.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7-1160x705.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-7.png 1198w\" ><\/figure>\n\n\n\n<p>We can observe from the image that the shaded submatrix denotes the maximum sum rectangle in the above example. The sum of elements in this submatrix gives us a value of 29.<\/p>\n\n\n\n<p><strong>Input 2:<\/strong><br><strong>Matrix =<\/strong><br>{{1, 0, 1, 0, 1},<br>{0, 1, 0, 1, 0},<br>{1, 0, 1, 0, 1},<br>{0, 1, 0, 1, 0}}<\/p>\n\n\n\n<p><strong>Output 2:<\/strong><br>(top, left) : (0, 0)<br>(bottom, right) : (3, 4)<br>10<br><strong>Explanation 2:<\/strong> The entire matrix will correspond to the maximum sum rectangle for this matrix.<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>The naive approach is to iterate over all the submatrices of the matrix and calculate the maximum rectangle sum over all the submatrices. We will use 4 nested loops to fix the corners of the rectangle\/submatrix, and then another 2 nested loops to calculate the sum of that submatrix.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/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 maxMatrixSum(vector &lt; vector &lt; int >> &amp; matrix) {\n  int n = matrix.size();\n  int m = matrix[0].size();\n  int maxSum = INT_MIN;\n  int top = 0, bottom = 0, left = 0, right = 0;\n  for (int i = 0; i &lt; n; i++) {\n    for (int j = 0; j &lt; m; j++) {\n      for (int k = 0; k &lt; n; k++) {\n        for (int l = 0; l &lt; m; l++) {\n          int currSum = 0;\n          for (int x = i; x &lt;= k; x++) {\n            for (int y = j; y &lt;= l; y++) {\n              currSum += matrix[x][y];\n            }\n          }\n          if (currSum > maxSum) {\n            maxSum = currSum;\n            top = i;\n            left = j;\n            right = k;\n            bottom = l;\n          }\n        }\n      }\n    }\n  }\n  cout &lt;&lt; \"The Top Left of the rectangle is: \" &lt;&lt; top &lt;&lt; \" \" &lt;&lt; left &lt;&lt; endl;\n  cout &lt;&lt; \"The Bottom Right of the rectangle is: \" &lt;&lt; bottom &lt;&lt; \" \" &lt;&lt; right &lt;&lt; endl;\n  cout &lt;&lt; \"The sum of this rectangle is: \" &lt;&lt; maxSum &lt;&lt; endl;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/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=\"\">public static void maxMatrixSum(int[][] matrix) {\n  int n = matrix.length;\n  int m = matrix[0].length;\n  int maxSum = -999999999;\n  int top = 0, bottom = 0, left = 0, right = 0;\n  for (int i = 0; i &lt; n; i++) {\n    for (int j = 0; j &lt; m; j++) {\n      for (int k = 0; k &lt; n; k++) {\n        for (int l = 0; l &lt; m; l++) {\n          int currSum = 0;\n          for (int x = i; x &lt;= k; x++) {\n for (int y = j; y &lt;= l; y++) {\n              currSum += matrix[x][y];\n            }\n          }\n          if (currSum > maxSum) {\n            maxSum = currSum;\n            top = i;\n            left = j;\n            right = k;\n            bottom = l;\n          }\n        }\n      }\n    }\n  }\n  System.out.println(\"The Top Left of the rectangle is: \" + top + \" \" + left);\n  System.out.println(\"The Bottom Right of the rectangle is: \" + bottom + \" \" + right);\n  System.out.println(\"The sum of the rectangle is: \" + maxSum);\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/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 maxMatrixSum(matrix):\n    maxSum = -9999999\n    n = len(matrix)\n    m = len(matrix[0])\n    top, left, right, bottom = None, None, None, None\n    for i in range(n):\n        for j in range(m):\n            for k in range(n):\n                for l in range(m):\n                    currSum = 0\n                    for x in range(i, k + 1):\n                        for y in range(j, l + 1):\n                            currSum += matrix[x][y]\n                    if currSum > maxSum:\n                        maxSum = currSum\n                        top = i\n                        left = j\n                        right = k\n                        bottom = l\n    print(\"The Top Left of the Rectangle is: \", top, left)\n    print(\"The Bottom Right of the Rectangle is: \", bottom, right)\n    print(\"The maximum sum is: \", maxSum)<\/pre>\n\n\n\n<p><strong>Complexity Analysis<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n<sup>6<\/sup>)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"optimal-approach\">Optimal Approach<\/h2>\n\n\n\n<p>We will use <strong>Kadane\u2019s Algorithm<\/strong> for finding the <strong>largest sum subarray<\/strong> (in 1D) to improve our time complexity over the naive approach. The key idea in this approach is that we will fix the <strong>left and right<\/strong> columns one by one and then for contiguous rows, we will find the maximum sum, for all possible choices of left and right column pairs with the help of Kadane\u2019s Algorithm. The algorithm is as follows:<\/p>\n\n\n\n<ul><li>Store the sum of elements in each row, from column, numbered <strong>left to right<\/strong>, in an array (<strong>stored[]<\/strong>)<\/li><li>By applying Kadane\u2019s Algorithm in this <strong>stored[] <\/strong>array, we will obtain the maximum sum subarray of this array, which is equal to the maximum sum, that can be obtained with column boundaries from <strong>left to right.<\/strong><\/li><li>To obtain the overall maximum sum, we take the maximum of all such values of sums obtained so far till the algorithm terminates.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"969\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3669 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-1024x969.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-1024x969.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-300x284.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-768x726.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-380x359.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-550x520.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-800x757.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6-1160x1097.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-6.png 1219w\" ><\/figure>\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=\"\">int kadaneAlgorithm(vector &lt; int > &amp; a, int &amp; start, int &amp; end, int n) {\n  int currSum = 0, maxSum = INT_MIN;\n  end = -1;\n  int currStart = 0;\n  for (int i = 0; i &lt; n; i++) {\n    currSum += a[i];\n    if (currSum &lt; 0) {\n      currSum = 0;\n      currStart = i + 1;\n    } else if (maxSum &lt; currSum) {\n      maxSum = currSum;\n      start = currStart;\n      end = i;\n    }\n  }\n  if (end != -1) {\n    return maxSum;\n  }\n  int index = max_element(a.begin(), a.end()) - a.begin();\n  start = end = index;\n  maxSum = * max_element(a.begin(), a.end());\n  return maxSum;\n}\nvoid maxMatrixSum(vector &lt; vector &lt; int >> &amp; matrix) {\n  int n = matrix.size();\n  int m = matrix[0].size();\n  int matrixLeft = -1, matrixRight = -1, matrixTop = -1, matrixBottom = -1;\n  int maxSum = INT_MIN;\n  vector &lt; int > stored(n);\n  int sum, start, end;\n  for (int left = 0; left &lt; m; left++) {\n    stored.assign(n, 0);\n    for (int right = left; right &lt; m; right++) {\n      for (int i = 0; i &lt; n; i++) {\n        stored[i] += matrix[i][right];\n      }\n      sum = kadaneAlgorithm(stored, start, end, n);\n      if (maxSum &lt; sum) {\n        maxSum = sum;\n        matrixLeft = left;\n        matrixRight = right;\n        matrixTop = start;\n        matrixBottom = end;\n      }\n    }\n  }\n  cout &lt;&lt; \"The Top Left of the rectangle is: \" &lt;&lt; matrixTop &lt;&lt; \" \" &lt;&lt; matrixLeft &lt;&lt; endl;\n  cout &lt;&lt; \"The Bottom Right of the rectangle is: \" &lt;&lt; matrixBottom &lt;&lt; \" \" &lt;&lt; matrixRight &lt;&lt; endl;\n  cout &lt;&lt; \"The sum of this rectangle is: \" &lt;&lt; maxSum &lt;&lt; endl;\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=\"\">public static void maxMatrixSum(int[][] matrix) {\n  int n = matrix.length;\n  int m = matrix[0].length;\n  int matrixLeft = -1, matrixRight = -1, matrixTop = -1, matrixBottom = -1;\n  int maxSum = Integer.MIN_VALUE;\n  int[] stored = new int[n];\n  int sum, start = 0, end;\n  for (int left = 0; left &lt; m; left++) {\n    Arrays.fill(stored, 0);\n    for (int right = left; right &lt; m; right++) {\n      for (int i = 0; i &lt; n; i++) {\n        stored[i] += matrix[i][right];\n      }\n      int currSum = 0, greatestSum = Integer.MIN_VALUE;\n      end = -1;\n      int currStart = 0;\n      for (int i = 0; i &lt; n; i++) {\n        currSum += stored[i];\n        if (currSum &lt; 0) {\n          currSum = 0;\n          currStart = i + 1;\n        } else if (maxSum &lt; currSum) {\n          greatestSum = currSum;\n          start = currStart;\n          end = i;\n        }\n      }\n      if (end != -1) {\n        sum = greatestSum;\n      } else {\n        start = 0;\n        end = 0;\n        greatestSum = stored[0];\n        for (int i = 0; i &lt; n; i++) {\n          if (greatestSum &lt; stored[i]) {\n            greatestSum = stored[i];\n            start = i;\n            end = i;\n          }\n        }\n        sum = greatestSum;\n      }\n      if (maxSum &lt; sum) {\n        maxSum = sum;\n        matrixLeft = left;\n        matrixRight = right;\n        matrixTop = start;\n        matrixBottom = end;\n      }\n  }\n  }\n  System.out.println(\"The Top Left of the rectangle is: \" + matrixTop + \" \" + matrixLeft);\n  System.out.println(\"The Bottom Right of the rectangle is: \" + matrixBottom + \" \" + matrixRight);\n  System.out.println(\"The sum of the rectangle is: \" + maxSum);\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 kadaneAlgorithm(a, start, end, n):\n    currSum = 0\n    maxSum = -9999999\n    end[0] = -1\n    currStart = 0\n    for i in range(n):\n        currSum += a[i]\n        if currSum &lt; 0:\n            currSum = 0\n            currStart = i + 1\n        elif maxSum &lt; currSum:\n            maxSum = currSum\n            start[0] = currStart\n            end[0] = i\n    if end[0] != -1:\n        return maxSum\n    maxSum = max(a)\n    for i in range(n):\n        if maxSum == a[i]:\n            start = i\n            end = i\n    return maxSum\n\n\ndef maxMatrixSum(matrix):\n    maxSum = -9999999\n    matrixLeft, matrixRight, matrixTop, matrixBottom = None, None, None, None\n    n = len(matrix)\n    m = len(matrix[0])\n stored = [0] * n\n    sum = 0\n    start = [0]\n    end = [0]\n    for left in range(m):\n        stored = [0] * n\n        for right in range(left, m):\n            for i in range(n):\n                stored[i] += matrix[i][right]\n            sum = kadaneAlgorithm(stored, start, end, n)\n            if sum > maxSum:\n                maxSum = sum\n                matrixLeft = left\n                matrixRight = right\n                matrixTop = start[0]\n                matrixBottom = end[0]\n    print(\"The Top Left of the Rectangle is: \", matrixTop, matrixLeft)\n    print(\"The Bottom Right of the Rectangle is: \", matrixBottom, matrixRight)\n    print(\"The maximum sum is: \", maxSum)<\/pre>\n\n\n\n<p><strong>Complexity Analysis<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n<sup>3<\/sup>)<\/li><li>Space Complexity: O(n)<\/li><\/ul>\n\n\n\n<h3 id=\"practice-problem\">Practice Problem<\/h3>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/old\/problems\/maximum-sum-square-submatrix\/\" target=\"_blank\">Maximum Sum Square Submatrix<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. What is Kadane\u2019s Algorithm used for?<\/strong><br>A. Kadane\u2019s Algorithm is used to find the largest sum subarray in a 1D array or list.<\/p>\n\n\n\n<p><strong>Q. Will this algorithm work if all the array elements are negative?<\/strong><br>A. Yes, even in that case the algorithm will work, and the result should be equal to the largest number in the array.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a 2D matrix, find the largest possible sum submatrix in it and print its value.&hellip;\n","protected":false},"author":5,"featured_media":3671,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","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":[559],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3604"}],"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=3604"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3604\/revisions"}],"predecessor-version":[{"id":3672,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3604\/revisions\/3672"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3671"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3604"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3604"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3604"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}