The concept rests on the innocent attitude. We find previous smaller and next smaller for the entire array in linear time instead of linearly finding previous smaller and next smaller for every element.
- Using a stack with index of preceding smaller element for every item, build an array perS[] in O(n) time.
- Using a stack with index of next smaller element for every item, create another array nextS[] in O(n) time.
- Please follow for every element hist[i]. With hist[i] as the lowest height, find the breadth of the biggest histogram. width = nextS[i] – prevS[i] – 1. < The region is now hist[i] times breadth.
- Step 3’s maximum of all values should be returned.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find next smaller for every element
vector<int> nextSmaller(vector<int>& hist) {
int n = hist.size();
// Initialize with n for the cases when next smaller
// does not exist
vector<int> nextS(n, n);
stack<int> st;
// Traverse all array elements from left to right
for (int i = 0; i < n; ++i) {
while (!st.empty() && hist[i] < hist[st.top()]) {
// Setting the index of the next smaller element
// for the top of the stack
nextS[st.top()] = i;
st.pop();
}
st.push(i);
}
return nextS;
}
// Function to find previous smaller for every element
vector<int> prevSmaller(vector<int>& hist) {
int n = hist.size();
// Initialize with -1 for the cases when prev smaller
// does not exist
vector<int> prevS(n, -1);
stack<int> st;
// Traverse all array elements from left to right
for (int i = 0; i < n; ++i) {
while (!st.empty() && hist[i] < hist[st.top()]) {
// Setting the index of the previous smaller element
// for the top of the stack
st.pop();
}
if (!st.empty()) {
prevS[i] = st.top();
}
st.push(i);
}
return prevS;
}
// Helper function to calculate the maximum rectangular
// area in the histogram
int getMaxArea(vector<int>& hist) {
vector<int> prevS = prevSmaller(hist);
vector<int> nextS = nextSmaller(hist);
int maxArea = 0;
// Calculate the area for each histogram bar
for (int i = 0; i < hist.size(); ++i) {
int width = nextS[i] - prevS[i] - 1;
int area = hist[i] * width;
maxArea = max(maxArea, area);
}
return maxArea;
}
int main() {
vector<int> hist = {60, 20, 50, 40, 10, 50, 60};
cout << getMaxArea(hist) << endl;
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
// Stack structure
struct Stack {
int top;
int capacity;
int* items;
};
// Function to create an empty stack with dynamic memory allocation
struct Stack* createStack(int capacity) {
struct Stack* stack =
(struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->items = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, int value) {
if (stack->top == stack->capacity - 1) {
printf("Stack overflow\n");
return;
}
stack->items[++(stack->top)] = value;
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow\n");
return -1;
}
return stack->items[(stack->top)--];
}
// Function to get the top element of the stack
int peek(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->items[stack->top];
}
return -1;
}
// Function to find the next smaller element for every element
void nextSmaller(int hist[], int n, int nextS[]) {
struct Stack* stack = createStack(n);
// Initialize with n for the cases
// when next smaller does not exist
for (int i = 0; i < n; i++) {
nextS[i] = n;
}
// Traverse all array elements from left to right
for (int i = 0; i < n; i++) {
while (!isEmpty(stack) && hist[i] < hist[peek(stack)]) {
nextS[peek(stack)] = i;
pop(stack);
}
push(stack, i);
}
}
// Function to find the previous smaller element for every element
void prevSmaller(int hist[], int n, int prevS[]) {
struct Stack* stack = createStack(n);
// Initialize with -1 for the cases when prev smaller does not exist
for (int i = 0; i < n; i++) {
prevS[i] = -1;
}
// Traverse all array elements from left to right
for (int i = 0; i < n; i++) {
while (!isEmpty(stack) && hist[i] < hist[peek(stack)]) {
pop(stack);
}
if (!isEmpty(stack)) {
prevS[i] = peek(stack);
}
push(stack, i);
}
}
// Helper function to calculate the maximum rectangular
// area in the histogram
int getMaxArea(int hist[], int n) {
int* prevS = (int*)malloc(n * sizeof(int));
int* nextS = (int*)malloc(n * sizeof(int));
int maxArea = 0;
// Find previous and next smaller elements
prevSmaller(hist, n, prevS);
nextSmaller(hist, n, nextS);
// Calculate the area for each histogram bar
for (int i = 0; i < n; i++) {
int width = nextS[i] - prevS[i] - 1;
int area = hist[i] * width;
if (area > maxArea) {
maxArea = area;
}
}
return maxArea;
}
// Driver code
int main() {
int hist[] = {60, 20, 50, 40, 10, 50, 60};
int n = sizeof(hist) / sizeof(hist[0]);
printf("Maximum Area: %d\n", getMaxArea(hist, n));
return 0;
}Java
import java.util.Stack;
class GfG {
// Function to find next smaller for every element
static int[] nextSmaller(int[] hist) {
int n = hist.length;
// Initialize with n for the cases when next smaller
// does not exist
int[] nextS = new int[n];
for (int i = 0; i < n; i++) {
nextS[i] = n;
}
Stack<Integer> st = new Stack<>();
// Traverse all array elements from left to right
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && hist[i] < hist[st.peek()]) {
// Setting the index of the next smaller element
// for the top of the stack
nextS[st.pop()] = i;
}
st.push(i);
}
return nextS;
}
// Function to find previous smaller for every element
static int[] prevSmaller(int[] hist) {
int n = hist.length;
// Initialize with -1 for the cases when prev smaller
// does not exist
int[] prevS = new int[n];
for (int i = 0; i < n; i++) {
prevS[i] = -1;
}
Stack<Integer> st = new Stack<>();
// Traverse all array elements from left to right
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && hist[i] < hist[st.peek()]) {
st.pop();
}
if (!st.isEmpty()) {
prevS[i] = st.peek();
}
st.push(i);
}
return prevS;
}
// Helper function to calculate the maximum rectangular
// area in the histogram
static int getMaxArea(int[] hist) {
int[] prevS = prevSmaller(hist);
int[] nextS = nextSmaller(hist);
int maxArea = 0;
// Calculate the area for each histogram bar
for (int i = 0; i < hist.length; i++) {
int width = nextS[i] - prevS[i] - 1;
int area = hist[i] * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
public static void main(String[] args) {
int[] hist = {60, 20, 50, 40, 10, 50, 60};
System.out.println(getMaxArea(hist));
}
}python
# Function to find next smaller for every element
def nextSmaller(hist):
n = len(hist)
# Initialize with n for the cases when next smaller
# does not exist
nextS = [n] * n
st = []
# Traverse all array elements from left to right
for i in range(n):
while st and hist[i] < hist[st[-1]]:
# Setting the index of the next smaller element
# for the top of the stack
nextS[st.pop()] = i
st.append(i)
return nextS
# Function to find previous smaller for every element
def prevSmaller(hist):
n = len(hist)
# Initialize with -1 for the cases when prev smaller
# does not exist
prevS = [-1] * n
st = []
# Traverse all array elements from left to right
for i in range(n):
while st and hist[i] < hist[st[-1]]:
st.pop()
if st:
prevS[i] = st[-1]
st.append(i)
return prevS
# Helper function to calculate the maximum rectangular
# area in the histogram
def getMaxArea(hist):
prevS = prevSmaller(hist)
nextS = nextSmaller(hist)
maxArea = 0
# Calculate the area for each histogram bar
for i in range(len(hist)):
width = nextS[i] - prevS[i] - 1
area = hist[i] * width
maxArea = max(maxArea, area)
return maxArea
# Driver code
hist = [60, 20, 50, 40, 10, 50, 60]
print(getMaxArea(hist))C#
using System;
using System.Collections.Generic;
class GfG {
// Function to find next smaller for every element
static int[] nextSmaller(int[] hist) {
int n = hist.Length;
// Initialize with n for the cases when next smaller
// does not exist
int[] nextS = new int[n];
for (int i = 0; i < n; i++) {
nextS[i] = n;
}
Stack<int> st = new Stack<int>();
// Traverse all array elements from left to right
for (int i = 0; i < n; i++) {
while (st.Count > 0 && hist[i] < hist[st.Peek()]) {
// Setting the index of the next smaller element
// for the top of the stack
nextS[st.Pop()] = i;
}
st.Push(i);
}
return nextS;
}
// Function to find previous smaller for every element
static int[] prevSmaller(int[] hist) {
int n = hist.Length;
// Initialize with -1 for the cases when prev smaller
// does not exist
int[] prevS = new int[n];
for (int i = 0; i < n; i++) {
prevS[i] = -1;
}
Stack<int> st = new Stack<int>();
// Traverse all array elements from left to right
for (int i = 0; i < n; i++) {
while (st.Count > 0 && hist[i] < hist[st.Peek()]) {
st.Pop();
}
if (st.Count > 0) {
prevS[i] = st.Peek();
}
st.Push(i);
}
return prevS;
}
// Helper function to calculate the maximum rectangular
// area in the histogram
static int getMaxArea(int[] hist) {
int[] prevS = prevSmaller(hist);
int[] nextS = nextSmaller(hist);
int maxArea = 0;
// Calculate the area for each histogram bar
for (int i = 0; i < hist.Length; i++) {
int width = nextS[i] - prevS[i] - 1;
int area = hist[i] * width;
maxArea = Math.Max(maxArea, area);
}
return maxArea;
}
static void Main() {
int[] hist = {60, 20, 50, 40, 10, 50, 60};
Console.WriteLine(getMaxArea(hist));
}
}JavaScript
// Function to find next smaller for every element
function nextSmaller(hist){
const n = hist.length;
// Initialize with n for the cases when next smaller
// does not exist
const nextS = new Array(n).fill(n);
const stack = [];
// Traverse all array elements from left to right
for (let i = 0; i < n; i++) {
while (stack.length
&& hist[i] < hist[stack[stack.length - 1]]) {
// Setting the index of the next smaller element
// for the top of the stack
nextS[stack.pop()] = i;
}
stack.push(i);
}
return nextS;
}
// Function to find previous smaller for every element
function prevSmaller(hist)
{
const n = hist.length;
// Initialize with -1 for the cases when prev smaller
// does not exist
const prevS = new Array(n).fill(-1);
const stack = [];
// Traverse all array elements from left to right
for (let i = 0; i < n; i++) {
while (stack.length
&& hist[i] < hist[stack[stack.length - 1]]) {
stack.pop();
}
if (stack.length) {
prevS[i] = stack[stack.length - 1];
}
stack.push(i);
}
return prevS;
}
// Helper function to calculate the maximum rectangular
// area in the histogram
function getMaxArea(hist)
{
const prevS = prevSmaller(hist);
const nextS = nextSmaller(hist);
let maxArea = 0;
// Calculate the area for each histogram bar
for (let i = 0; i < hist.length; i++) {
const width = nextS[i] - prevS[i] - 1;
const area = hist[i] * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
// Driver code
const hist = [60, 20, 50, 40, 10, 50, 60];
console.log(getMaxArea(hist));