{"id":3925,"date":"2021-11-18T15:00:23","date_gmt":"2021-11-18T09:30:23","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3925"},"modified":"2021-11-18T15:00:38","modified_gmt":"2021-11-18T09:30:38","slug":"largest-rectangle-in-histogram","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/largest-rectangle-in-histogram\/","title":{"rendered":"Largest Rectangle in Histogram"},"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=\"#approach-1-brute-force\">Approach 1: Brute Force<\/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-divide-and-conquer\">Approach 2: Divide and Conquer<\/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-3-stack\">Approach 3: Stack<\/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=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given an array of integers <strong>A[]<\/strong>, where each element <strong>A[i]<\/strong> represents the height of a bar in histogram. The width of each bar is <strong>1<\/strong>. The task is to return the area of the largest histogram.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"407\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"input\"  class=\"wp-image-3965 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\/input-1024x407.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1024x407.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-300x119.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-768x305.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1536x611.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-380x151.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-550x219.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-800x318.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input-1160x461.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/input.png 1693w\" ><\/figure>\n\n\n\n<p>Output: 10<br><strong>Explanation: <\/strong>Shown in image<br><strong>Input:&nbsp;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"634\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"output\"  class=\"wp-image-3967 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 634px) 100vw, 634px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-634x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-634x1024.png 634w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-186x300.png 186w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-768x1240.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-380x614.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-550x888.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output-800x1292.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/output.png 865w\" ><\/figure>\n\n\n\n<p><strong>Output:<\/strong> 4<br><strong>Explanation: <\/strong>Shown in image<\/p>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>The key idea to observe is that the height of the maximum area of the histogram formed between any two bars will always be bounded by the height of the shortest bar lying between them. Observe the below image.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"671\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Brute Force\"  class=\"wp-image-3968 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\/Brute-Force-1-1024x671.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-1024x671.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-300x197.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-768x503.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-1536x1006.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-380x249.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-230x150.png 230w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-260x170.png 260w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-550x360.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-800x524.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1-1160x760.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-1.png 1693w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a variable,<strong> maxArea = 0<\/strong>, denoting the maximum area of the histogram to be found.<\/li><li>Run two nested loops from <strong>i = 0<\/strong> till <strong>i = N<\/strong> and from <strong>j = i<\/strong> till <strong>j = N<\/strong>.<\/li><li>For each <strong>jth<\/strong> iteration<strong>, <\/strong>run a loop <strong>k = i<\/strong> till <strong>k = j<\/strong> and find the height of the minimum bar among them.<\/li><li>The area of the histogram would be <strong>minHeight * (j &#8211; i + 1).<\/strong><\/li><li>Maximize <strong>maxArea<\/strong>.<\/li><\/ul>\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=\"\">int largestRectangleArea(vector &lt; int > &amp; heights) {\n  int max_area = 0;\n  for (size_t i = 0; i &lt; heights.size(); i++) {\n    for (size_t j = i; j &lt; heights.size(); j++) {\n      int min_height = INT_MAX;\n      for (size_t k = i; k &lt;= j; k++) {\n        min_height = min(min_height, heights[k]);\n      }\n      max_area = max(max_area, min_height * (j - i + 1));\n    }\n  }\n  return max_area;\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=\"\"> public int largestRectangleArea(int[] heights) {\n  int maxarea = 0;\n  for (int i = 0; i &lt; heights.length; i++) {\n    for (int j = i; j &lt; heights.length; j++) {\n      int minheight = Integer.MAX_VALUE;\n      for (int k = i; k &lt;= j; k++)\n        minheight = Math.min(minheight, heights[k]);\n      maxarea = Math.max(maxarea, minheight * (j - i + 1));\n    }\n  }\n  return maxarea;\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 largestRectangleArea(heights):\n    max_area = 0\n    for i in range(len(heights)):\n        for j in range(i, len(heights)):\n            min_height = inf\n            for k in range(i, j + 1):\n                min_height = min(min_height, heights[k])\n            max_area = max(max_area, min_height * (j - i + 1))\n    return max_area<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^3), where N is the size of the array<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<h2 id=\"approach-2-divide-and-conquer\">Approach 2: Divide and Conquer<\/h2>\n\n\n\n<p>Instead of traversing through all the elements from <strong>A[i]<\/strong> and <strong>A[j]<\/strong> again, the idea is to use <strong>divide and conquer<\/strong> algorithm.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"973\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Divide and Conquer\"  class=\"wp-image-3969 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\/Divide-and-Conquer-1024x973.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-1024x973.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-300x285.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-768x730.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-1536x1459.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-2048x1946.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-380x361.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-550x523.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-800x760.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer-1160x1102.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Divide-and-Conquer.png 2161w\" ><\/figure>\n\n\n\n<p>Let us think, how can we obtain the rectangle with maximum area in the histogram.<br>If you observe clearly, it is based upon these three ideas:<\/p>\n\n\n\n<ul><li>The rectangle with the widest possible width and height equal to the shortest bar.<\/li><li>The area of the rectangle formed on the left side of the minimum height.<\/li><li>The area of the rectangle formed on the right side of the minimum height.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-3\">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=\"\">int calculateArea(vector &lt; int > &amp; heights, int start, int end) {\n  if (start > end) {\n    return 0;\n  }\n  int min_index = start;\n  for (int i = start; i &lt;= end; i++) {\n    if (heights[min_index] > heights[i]) {\n      min_index = i;\n    }\n  }\n  return max({\n    heights[min_index] * (end - start + 1),\n    calculateArea(heights, start, min_index - 1),\n    calculateArea(heights, min_index + 1, end)\n  });\n}\n \nint largestRectangleArea(vector &lt; int > &amp; heights) {\n  return calculateArea(heights, 0, heights.size() - 1);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-3\">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=\"\">public int calculateArea(int[] heights, int start, int end) {\n  if (start > end)\n    return 0;\n  int minindex = start;\n  for (int i = start; i &lt;= end; i++)\n    if (heights[minindex] > heights[i])\n      minindex = i;\n  return Math.max(heights[minindex] * (end - start + 1),\n    Math.max(calculateArea(heights, start, minindex - 1),\n      calculateArea(heights, minindex + 1, end))\n  );\n}\n \npublic int largestRectangleArea(int[] heights) {\n  return calculateArea(heights, 0, heights.length - 1);\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-3\">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 largestRectangleArea(heights) -> int:\n    def calculateArea(heights: List[int], start: int, end: int) -> int:\n        if start > end:\n            return 0\n        min_index = start\n        for i in range(start, end + 1):\n            if heights[min_index] > heights[i]:\n                min_index = i\n        return max(\n            heights[min_index] * (end - start + 1),\n            calculateArea(heights, start, min_index - 1),\n            calculateArea(heights, min_index + 1, end),\n        )\n \n    return calculateArea(heights, 0, len(heights) - 1)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(NlogN), where N is the size of the array<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N), since array is used.<\/p>\n\n\n\n<h2 id=\"approach-3-stack\">Approach 3: Stack<\/h2>\n\n\n\n<p>The idea is similar to finding the <strong>Next Greater element <\/strong>using stack. In this problem, instead of finding the <strong>next greater element<\/strong>, we will maintain two arrays <strong>left[] <\/strong>and <strong>right[]<\/strong> denoting the smaller elements on the left and right. Look at the animation below for better understanding:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"612\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Stack\"  class=\"wp-image-3970 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\/Stack-1024x612.gif\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-1024x612.gif 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-300x179.gif 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-768x459.gif 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-1536x918.gif 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-380x227.gif 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-550x329.gif 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-800x478.gif 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-1160x693.gif 1160w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a stack <strong>S<\/strong>.<\/li><li>Push the first index of <strong>A[] <\/strong>into the stack.<\/li><li>Traverse through the array <strong>A[]<\/strong> and compare the height of <strong>A[i] <\/strong>with the height at the top of the stack.<\/li><li>If the height is:<ul><li>Greater than <strong>A[S.top()]<\/strong>, push it into the stack.<\/li><li>Less than <strong>A[S.top()]<\/strong>, keep popping the elements until <strong>A[i] &gt;= A[S.top()].<\/strong><\/li><\/ul><\/li><li>Keep maximizing the area while popping the elements from the stack.<\/li><li>Push the index <strong>i<\/strong> for each element.<\/li><li>Return the maximum element.<\/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=\"\">int largestRectangleArea(vector &lt; int > &amp; heights) {\n  stack &lt; int > stk;\n  stk.push(-1);\n  int max_area = 0;\n  for (size_t i = 0; i &lt; heights.size(); i++) {\n    while (stk.top() != -1 and heights[stk.top()] >= heights[i]) {\n      int current_height = heights[stk.top()];\n      stk.pop();\n      int current_width = i - stk.top() - 1;\n      max_area = max(max_area, current_height * current_width);\n    }\n    stk.push(i);\n  }\n  while (stk.top() != -1) {\n    int current_height = heights[stk.top()];\n    stk.pop();\n    int current_width = heights.size() - stk.top() - 1;\n    max_area = max(max_area, current_height * current_width);\n  }\n  return max_area;\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 int largestRectangleArea(int[] heights) {\n   Deque &lt; Integer > stack = new ArrayDeque &lt; > ();\n   stack.push(-1);\n   int length = heights.length;\n   int maxArea = 0;\n   for (int i = 0; i &lt; length; i++) {\n     while ((stack.peek() != -1) &amp;&amp;\n       (heights[stack.peek()] >= heights[i])) {\n       int currentHeight = heights[stack.pop()];\n       int currentWidth = i - stack.peek() - 1;\n       maxArea = Math.max(maxArea, currentHeight * currentWidth);\n     }\n     stack.push(i);\n   }\n   while (stack.peek() != -1) {\n     int currentHeight = heights[stack.pop()];\n     int currentWidth = length - stack.peek() - 1;\n     maxArea = Math.max(maxArea, currentHeight * currentWidth);\n   }\n   return maxArea;\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 largestRectangleArea(self, heights):\n    stack = [-1]\n    max_area = 0\n    for i in range(len(heights)):\n        while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:\n            current_height = heights[stack.pop()]\n            current_width = i - stack[-1] - 1\n            max_area = max(max_area, current_height * current_width)\n        stack.append(i)\n \n    while stack[-1] != -1:\n        current_height = heights[stack.pop()]\n        current_width = len(heights) - stack[-1] - 1\n        max_area = max(max_area, current_height * current_width)\n    return max_area<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is the size of the array<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N), since stack is used.<\/p>\n\n\n\n<p id=\"-practice-questions-\"><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/largest-rectangle-in-histogram\/\" target=\"_blank\" rel=\"noreferrer noopener\">Largest Rectangle in Histogram<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>Can the brute force approach be improved?<br><\/strong>Yes, we can run two nested loops and find the minimum height on both left and right half while iterating and maximizing the area. The time complexity would be O(N^2).<br><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given an array of integers A[], where each element A[i] represents the height of a bar in histogram.&hellip;\n","protected":false},"author":5,"featured_media":3971,"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":[590],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3925"}],"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=3925"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3925\/revisions"}],"predecessor-version":[{"id":3978,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3925\/revisions\/3978"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3971"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3925"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3925"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3925"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}