{"id":"dd98b21b-00e1-4d3e-9702-553a4f093b1c","name":"Largest Area Histogram","description":"<p>1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing the height of bars in a bar chart. 3. You are required to find and print the area of largest rectangle in the histogram. e.g. for the array [6 2 5 4 5 1 6] -&gt; 12</p>","inputFormat":"<p>Input is managed for you</p>","outputFormat":"<p>A number representing area of largest rectangle in histogram</p>","constraints":"<p>0 &lt;= n &lt; 20 0 &lt;= a[i] &lt;= 10</p>","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\nint main(int argc, char **argv)\n{ \n int n;\n cin>>n;\n vector<int>arr(n,0);\n for(int i=0;i<n;i++)\n {\n cin>>arr[i];\n }\n //write your code here\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main{\r\n \r\n\r\npublic static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(br.readLine());\r\n int[] a = new int[n];\r\n for(int i = 0; i < n; i++){\r\n a[i] = Integer.parseInt(br.readLine());\r\n }\r\n\r\n // code\r\n }\r\n}"},"python":{"code":"from sys import stdin\nn = int(input())\narr =[]\nfor i in range (n):\n x = int(input())\n arr.append(x)\n\n#write your code here"}},"points":10,"difficulty":"hard","sampleInput":"7\r\n6\r\n2\r\n5\r\n4\r\n5\r\n1\r\n6","sampleOutput":"12","questionVideo":"https://www.youtube.com/embed/m01ubOp-FMg","hints":[],"associated":[{"id":"a80bdb09-d386-47b1-84ff-44f611218182","name":"What do we store in the next smallest left and right arrays?(Q- Largest Area Histogram)","slug":"what-do-we-store-in-the-next-smallest-left-and-right-arrays-q-largest-area-histogram","type":4},{"id":"ee1df7e7-a106-4e25-99bb-1cbba90d6d64","name":"Why is this question done using stacks?(Q- Largest Area Histogram)","slug":"why-is-this-question-done-using-stacks-q-largest-area-histogram","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9847c2b3-e3ad-4b1c-97d1-00206b1be68d","name":"Stacks And Queues For Beginners","slug":"stacks-and-queues-for-beginners","type":0},{"id":"e835a47e-d5c6-4a8c-85f4-6bb6503d2965","name":"Largest Area Histogram","slug":"largest-area-histogram","type":1}],"next":{"id":"516201b8-a329-4dd6-a5d3-22ecad87e1da","name":"Largest Area Histogram","type":3,"slug":"largest-area-histogram"},"prev":{"id":"c9450d1a-a173-4840-a8e0-eb884062da41","name":"Stock Span","type":3,"slug":"stock-span"}}}

Largest Area Histogram

<p>1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing the height of bars in a bar chart. 3. You are required to find and print the area of largest rectangle in the histogram. e.g. for the array [6 2 5 4 5 1 6] -&gt; 12</p>

{"id":"dd98b21b-00e1-4d3e-9702-553a4f093b1c","name":"Largest Area Histogram","description":"<p>1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing the height of bars in a bar chart. 3. You are required to find and print the area of largest rectangle in the histogram. e.g. for the array [6 2 5 4 5 1 6] -&gt; 12</p>","inputFormat":"<p>Input is managed for you</p>","outputFormat":"<p>A number representing area of largest rectangle in histogram</p>","constraints":"<p>0 &lt;= n &lt; 20 0 &lt;= a[i] &lt;= 10</p>","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\nint main(int argc, char **argv)\n{ \n int n;\n cin>>n;\n vector<int>arr(n,0);\n for(int i=0;i<n;i++)\n {\n cin>>arr[i];\n }\n //write your code here\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main{\r\n \r\n\r\npublic static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(br.readLine());\r\n int[] a = new int[n];\r\n for(int i = 0; i < n; i++){\r\n a[i] = Integer.parseInt(br.readLine());\r\n }\r\n\r\n // code\r\n }\r\n}"},"python":{"code":"from sys import stdin\nn = int(input())\narr =[]\nfor i in range (n):\n x = int(input())\n arr.append(x)\n\n#write your code here"}},"points":10,"difficulty":"hard","sampleInput":"7\r\n6\r\n2\r\n5\r\n4\r\n5\r\n1\r\n6","sampleOutput":"12","questionVideo":"https://www.youtube.com/embed/m01ubOp-FMg","hints":[],"associated":[{"id":"a80bdb09-d386-47b1-84ff-44f611218182","name":"What do we store in the next smallest left and right arrays?(Q- Largest Area Histogram)","slug":"what-do-we-store-in-the-next-smallest-left-and-right-arrays-q-largest-area-histogram","type":4},{"id":"ee1df7e7-a106-4e25-99bb-1cbba90d6d64","name":"Why is this question done using stacks?(Q- Largest Area Histogram)","slug":"why-is-this-question-done-using-stacks-q-largest-area-histogram","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9847c2b3-e3ad-4b1c-97d1-00206b1be68d","name":"Stacks And Queues For Beginners","slug":"stacks-and-queues-for-beginners","type":0},{"id":"e835a47e-d5c6-4a8c-85f4-6bb6503d2965","name":"Largest Area Histogram","slug":"largest-area-histogram","type":1}],"next":{"id":"516201b8-a329-4dd6-a5d3-22ecad87e1da","name":"Largest Area Histogram","type":3,"slug":"largest-area-histogram"},"prev":{"id":"c9450d1a-a173-4840-a8e0-eb884062da41","name":"Stock Span","type":3,"slug":"stock-span"}}}
plane

Editor

Loading...

Largest Area Histogram

hard

1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing the height of bars in a bar chart. 3. You are required to find and print the area of largest rectangle in the histogram. e.g. for the array [6 2 5 4 5 1 6] -> 12

Constraints

0 <= n < 20 0 <= a[i] <= 10

Format

Input

Input is managed for you

Output

A number representing area of largest rectangle in histogram

Example

Sample Input

7 6 2 5 4 5 1 6

Sample Output

12

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode