{"id":27592,"date":"2018-04-04T19:32:54","date_gmt":"2018-04-04T14:02:54","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27592"},"modified":"2018-04-04T19:32:54","modified_gmt":"2018-04-04T14:02:54","slug":"largest-rectangular-area-histogram-set-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/largest-rectangular-area-histogram-set-2\/","title":{"rendered":"Largest Rectangular Area in a Histogram | Set 2"},"content":{"rendered":"<p>Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.<span id=\"more-116498\"><\/span><\/p>\n<p>For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 2, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)<\/p>\n<p>We have discussed a Divide and Conquer based O(nLogn) solution for this problem. In this post, O(n) time solution is discussed. Like the previous post, width of all bars is assumed to be 1 for simplicity. For every bar \u2018x\u2019, we calculate the area with \u2018x\u2019 as the smallest bar in the rectangle. If we calculate such area for every bar \u2018x\u2019 and find the maximum of all areas, our task is done. How to calculate area with \u2018x\u2019 as smallest bar? We need to know index of the first smaller (smaller than \u2018x\u2019) bar on left of \u2018x\u2019 and index of first smaller bar on right of \u2018x\u2019. Let us call these indexes as \u2018left index\u2019 and \u2018right index\u2019 respectively.<br \/>\nWe traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar \u2013 the current index tells us the \u2018right index\u2019 and index of previous item in stack is the \u2018left index\u2019. Following is the complete algorithm.<\/p>\n<p><strong>1) <\/strong>Create an empty stack.<\/p>\n<p><strong>2) <\/strong>Start from first bar, and do following for every bar \u2018hist[i]\u2019 where \u2018i\u2019 varies from 0 to n-1.<br \/>\n\u2026\u2026<strong>a)<\/strong> If stack is empty or hist[i] is higher than the bar at top of stack, then push \u2018i\u2019 to stack.<br \/>\n\u2026\u2026<strong>b)<\/strong> If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the \u2018left index\u2019 is previous (previous to tp) item in stack and \u2018right index\u2019 is \u2018i\u2019 (current index).<\/p>\n<p><strong>3)<\/strong> If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.<\/p>\n<p>Following is C++ implementation of the above algorithm.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20maximum%20rectangular%20area%20in%20linear%20time%0A%23include%3Ciostream%3E%0A%23include%3Cstack%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20The%20main%20function%20to%20find%20the%20maximum%20rectangular%20area%20under%20given%0A%2F%2F%20histogram%20with%20n%20bars%0Aint%20getMaxArea(int%20hist%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20an%20empty%20stack.%20The%20stack%20holds%20indexes%20of%20hist%5B%5D%20array%0A%20%20%20%20%2F%2F%20The%20bars%20stored%20in%20stack%20are%20always%20in%20increasing%20order%20of%20their%0A%20%20%20%20%2F%2F%20heights.%0A%20%20%20%20stack%3Cint%3E%20s%3B%0A%20%0A%20%20%20%20int%20max_area%20%3D%200%3B%20%2F%2F%20Initalize%20max%20area%0A%20%20%20%20int%20tp%3B%20%20%2F%2F%20To%20store%20top%20of%20stack%0A%20%20%20%20int%20area_with_top%3B%20%2F%2F%20To%20store%20area%20with%20top%20bar%20as%20the%20smallest%20bar%0A%20%0A%20%20%20%20%2F%2F%20Run%20through%20all%20bars%20of%20given%20histogram%0A%20%20%20%20int%20i%20%3D%200%3B%0A%20%20%20%20while%20(i%20%3C%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20this%20bar%20is%20higher%20than%20the%20bar%20on%20top%20stack%2C%20push%20it%20to%20stack%0A%20%20%20%20%20%20%20%20if%20(s.empty()%20%7C%7C%20hist%5Bs.top()%5D%20%3C%3D%20hist%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20s.push(i%2B%2B)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20this%20bar%20is%20lower%20than%20top%20of%20stack%2C%20then%20calculate%20area%20of%20rectangle%20%0A%20%20%20%20%20%20%20%20%2F%2F%20with%20stack%20top%20as%20the%20smallest%20(or%20minimum%20height)%20bar.%20\u2019i\u2019%20is%20%0A%20%20%20%20%20%20%20%20%2F%2F%20\u2019right%20index\u2019%20for%20the%20top%20and%20element%20before%20top%20in%20stack%20is%20\u2019left%20index\u2019%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20tp%20%3D%20s.top()%3B%20%20%2F%2F%20store%20the%20top%20index%0A%20%20%20%20%20%20%20%20%20%20%20%20s.pop()%3B%20%20%2F%2F%20pop%20the%20top%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20the%20area%20with%20hist%5Btp%5D%20stack%20as%20smallest%20bar%0A%20%20%20%20%20%20%20%20%20%20%20%20area_with_top%20%3D%20hist%5Btp%5D%20*%20(s.empty()%20%3F%20i%20%3A%20i%20-%20s.top()%20-%201)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20update%20max%20area%2C%20if%20needed%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(max_area%20%3C%20area_with_top)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20max_area%20%3D%20area_with_top%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Now%20pop%20the%20remaining%20bars%20from%20stack%20and%20calculate%20area%20with%20every%0A%20%20%20%20%2F%2F%20popped%20bar%20as%20the%20smallest%20bar%0A%20%20%20%20while%20(s.empty()%20%3D%3D%20false)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20tp%20%3D%20s.top()%3B%0A%20%20%20%20%20%20%20%20s.pop()%3B%0A%20%20%20%20%20%20%20%20area_with_top%20%3D%20hist%5Btp%5D%20*%20(s.empty()%20%3F%20i%20%3A%20i%20-%20s.top()%20-%201)%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(max_area%20%3C%20area_with_top)%0A%20%20%20%20%20%20%20%20%20%20%20%20max_area%20%3D%20area_with_top%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20max_area%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20hist%5B%5D%20%3D%20%7B6%2C%202%2C%205%2C%204%2C%205%2C%201%2C%206%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(hist)%2Fsizeof(hist%5B0%5D)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Maximum%20area%20is%20%22%20%3C%3C%20getMaxArea(hist%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Maximum area is 12<\/pre>\n<p><strong>Time Complexity: <\/strong>Since every bar is pushed and popped only once, the time complexity of this method is O(n).<\/p>\n","protected":false},"excerpt":{"rendered":"<p> Largest Rectangular Area in a Histogram | Set 2 &#8211; Stack &#8211; Find the largest rectangular area possible in a given histogram where the largest rectangle<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[81785,81782,81788,81784,81781,81787,81783,81789,81790,81786,81780],"class_list":["post-27592","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","tag-largest-rectangle-hackerrank-solution","tag-largest-rectangle-in-histogram-algorithm","tag-largest-rectangle-in-histogram-divide-and-conquer","tag-largest-rectangle-in-histogram-leetcode-c","tag-largest-rectangle-in-histogram-python","tag-largest-rectangular-area-in-a-histogram","tag-largest-rectangular-area-in-a-histogram-divide-and-conquer","tag-largest-rectangular-area-in-a-histogram-leetcode","tag-max-rectangle-in-binary-matrix","tag-maximum-histogram-area-leetcode","tag-maximum-rectangular-area-in-a-matrix"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27592","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27592"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27592\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27592"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27592"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27592"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}