{"id":"c7971540-6fe4-4d09-98da-ab9ea6e9fc42","name":"Largest Area Histogram 2","description":"1. You are given a number n, representing the size of array a.\r\n2. You are given n numbers, representing the height of bars in a bar chart.\r\n3. You are required to find and print the area of largest rectangle in the histogram.\r\n\r\nChallenge. Could u solve it in one iteration.\r\nNote. This question is same as Largest Area Histogram just the constrains are higher.\r\n","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= heights.length &lt;= 10^5\r\n2. 0 &lt;= heights[i] &lt;= 10^4","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n\nint largestRectangleArea(vector<int>&heights){\n \n}\n\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 cout<<largestRectangleArea(arr);\n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static int largestRectangleArea(int[] heights) {\r\n return 0;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n int heights[] = new int[n];\r\n for(int i=0;i<n;i++)heights[i] = Integer.parseInt(read.readLine());\r\n\r\n System.out.println(largestRectangleArea(heights));\r\n \r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"6\r\n2\r\n1\r\n5\r\n6\r\n2\r\n3","sampleOutput":"10\r\n","questionVideo":"","hints":[],"associated":[],"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":"8c6022a5-8654-4226-918f-8110af738bd4","name":"Stacks For Intermediate","slug":"stacks-for-intermediate-688","type":0},{"id":"d6630306-e02b-48a4-b4d1-173b741f518d","name":"Largest Area Histogram 2","slug":"largest-area-histogram-2","type":1}],"next":{"id":"a9a5be62-050b-44c2-abf8-3bea5babb33c","name":"Largest Area Histogram 2 MCQ","type":0,"slug":"largest-area-histogram-2-mcq"},"prev":{"id":"1f49192b-118b-4341-9c43-52275b689d1e","name":"Next greater element II.","type":3,"slug":"next-greater-element-ii"}}}

Largest Area Histogram 2

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. Challenge. Could u solve it in one iteration. Note. This question is same as Largest Area Histogram just the constrains are higher.

{"id":"c7971540-6fe4-4d09-98da-ab9ea6e9fc42","name":"Largest Area Histogram 2","description":"1. You are given a number n, representing the size of array a.\r\n2. You are given n numbers, representing the height of bars in a bar chart.\r\n3. You are required to find and print the area of largest rectangle in the histogram.\r\n\r\nChallenge. Could u solve it in one iteration.\r\nNote. This question is same as Largest Area Histogram just the constrains are higher.\r\n","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= heights.length &lt;= 10^5\r\n2. 0 &lt;= heights[i] &lt;= 10^4","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n\nint largestRectangleArea(vector<int>&heights){\n \n}\n\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 cout<<largestRectangleArea(arr);\n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static int largestRectangleArea(int[] heights) {\r\n return 0;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n int heights[] = new int[n];\r\n for(int i=0;i<n;i++)heights[i] = Integer.parseInt(read.readLine());\r\n\r\n System.out.println(largestRectangleArea(heights));\r\n \r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"6\r\n2\r\n1\r\n5\r\n6\r\n2\r\n3","sampleOutput":"10\r\n","questionVideo":"","hints":[],"associated":[],"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":"8c6022a5-8654-4226-918f-8110af738bd4","name":"Stacks For Intermediate","slug":"stacks-for-intermediate-688","type":0},{"id":"d6630306-e02b-48a4-b4d1-173b741f518d","name":"Largest Area Histogram 2","slug":"largest-area-histogram-2","type":1}],"next":{"id":"a9a5be62-050b-44c2-abf8-3bea5babb33c","name":"Largest Area Histogram 2 MCQ","type":0,"slug":"largest-area-histogram-2-mcq"},"prev":{"id":"1f49192b-118b-4341-9c43-52275b689d1e","name":"Next greater element II.","type":3,"slug":"next-greater-element-ii"}}}
plane

Editor


Loading...

Largest Area Histogram 2

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. Challenge. Could u solve it in one iteration. Note. This question is same as Largest Area Histogram just the constrains are higher.

Constraints

1. 1 <= heights.length <= 10^5 2. 0 <= heights[i] <= 10^4

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

6 2 1 5 6 2 3

Sample Output

10

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode