The Maximum Rectangular Area in a Histogram in Java

Continuous bars should be used to form the largest possible rectangle. We'll assume in the interest of convenience that each bar's width is 1.

Naive Approach

In this method, each bar will be taken into account as the initial point one at a time, and from there, the rectangle area will be computed again by taking the subsequent bars one at a time. Every time the rectangle area is calculated, it is compared to the greatest area currently available 

Example program

// program for the maximum rectangular area in a histogram in java using a naive approach

public class LargestRectArea
{  
int findMin(int a, int b)  
{  
  int min = (a > b) ? b : a;   
  return min;  
}  
int findMax(int a, int b)  
{  
  int max = (a > b) ? a : b;   
  return max;  
}  
public static void main(String argvs[])  
{  
LargestRectAreaobj = new LargestRectArea();  
int arr[] = {8, 4, 7, 6, 7, 3, 7};  
int n = arr.length;  
 int maxArea = 0;  
for(int i = 0; i< n; i++)  
{  
int temp = arr[i];  
maxArea = obj.findMax(temp, maxArea);  
for(int j = i + 1; j < n; j++)  
{  
    temp = obj.findMin(temp, arr[j]);  
maxArea = obj.findMax(maxArea, temp * (j - i + 1));  
}  
}  
System.out.println("The maximum rectangular area is: " + maxArea);  
}  
}   

Output

The maximum rectangular area is: 21

Analysis of complexity

Time Complexity: We utilized nested for-loops of degree 2 in the program above. As a result, the program described above has an overall complexity of O(n2), where n represents the number of entries in the given array.

Divide and Conquer Approach

The idea is to locate the index of the least level in the input array. The greatest area is the largest of the next three values after we have determined the indices of the number that is minimum.

• A maximum area is located to the left of the lower limit 
• maximum-sized region to the right of the lower limit 
• multiplied by the lowest bar value, the total number of bars.

Example program

//program for the maximum rectangular area in a histogram in java using the divide and conquer technique

import java.util.*;  
public class LargestRectArea1  
{  
static int hist[];  
static int segTree[];  
public int max(int a, int b, int c)  
{ returnMath.max(Math.max(a, b), c); } 
public int findMin(int a, int b)  
{  
if (a == -1)  
{ return b; }  
if (b == -1) { return a; }  
return (hist[a] < hist[b]) ? a : b;  
}  
public int findMid(int s, int e)  
{ return s + (e - s) / 2; }
public int findIndexUtility( intsi, int ei, int qs, int qe, int idx)  
{  
if (qs<= si&&qe>= ei)  
{  
return segTree[idx];  
} 
if (ei<qs || si>qe)  
{  
return -1;  
} 
int mid = findMid(si, ei);  
return findMin( findIndexUtility(si, mid, qs, qe, 2 * idx + 1),  
findIndexUtility( mid + 1, ei, qs, qe, 2 * idx + 2));  
}  
public int returnIndex( int s, int qb, int qe)  
{  
if (qb< 0 || qe> s - 1 || qb>qe)  
{  
System.out.print("The given input is not valid");  
return -1;  
}  


return findIndexUtility( 0, s - 1, qb, qe, 0);  
}  
public int constructSTUtililty(int s, int e, int si)  
{ 
if (s == e)  
{  
return (segTree[si] = s);  
} 
int mid = findMid(s, e);  
segTree[si] = findMin(constructSTUtililty(s, mid, si * 2 + 1),  
constructSTUtililty(mid + 1, e, si * 2 + 2));  
return segTree[si];  
} 
public void constructSegTree(int s)  
{ 
int x = (int)(Math.ceil(Math.log(s)));
int maxSize = 2 * (int)Math.pow(2, x) - 1;
segTree = new int[maxSize * 2];  
constructSTUtililty( 0, s - 1, 0);  
} 
public int findMaxAreaRec( int s, int lt, int rt)  
{ 
if (lt>rt)  returnInteger.MIN_VALUE;  
if (lt == rt)  return hist[lt]; 
int i = returnIndex(s, lt, rt);  
return max(findMaxAreaRec(s, lt, i - 1), findMaxAreaRec( s, i + 1, rt), (rt - lt + 1) * (hist[i]));  
}  
public int computeMaxArea( int s)  
{  
constructSegTree(s);  
return findMaxAreaRec(s, 0, s - 1);  
}  
public static void main(String[] argvs)  
{  
int[] arr = {7, 2, 6, 5, 6, 2, 7};  
int s = arr.length;  
hist = new int[s];  
LargestRectArea1 obj = new LargestRectArea1();  
hist = arr;  
System.out.println("The maximum rectangular area is: " + obj.computeMaxArea(s));  
}  
}   

Output

The maximum rectangular area is: 15

Analysis of complexity

The above program's time complexity depends on the segment tree and locating the largest rectangle area, respectively. The segment tree construction process takes O(n) time, whereas determining the largest rectangle region takes O(log(n)) time. As a result, the time complexity changes to O(n) + O(n*log(n)), and asymptotically, it changes to O(n*log(n)), where n is the maximum number of entries in the input array.

Using Stack

Let's examine the stack-based approach for locating the rectangle area.

Step 1: A stack is the first step in pushing and popping items.

Step 2: Starting with the first bar, complete the task "histArr[j]" for each subsequent bar, where "j" ranges from 0 to s–1.

Push "j" to the stack if there are no elements in the stack or if histArr[ij] is longer than the bar at the top of the stack.

Continue popping bars from the top of the stack until the bar at the top of the stack is higher if the existing bar is smaller than the bar that is existing there. Assume that histArr[top] is the removed bar. Calculate the rectangle's area using the smallest bar, histArr[top]. The preceding bar in the stack is the "left index" for the histArr[top], and the "right index" is "j." (the current index).

Step 3: If indeed the stack contains any bars, remove them one at a time from the stack by repeating step 2(ii) for each bar that was taken out.

Example program

import java.util.Stack;
public class LargestRectArea2  
{ 
public int findMaxArea(int histArr[], int s)  
{ 
Stack<Integer>stk = new Stack<>();  


int maxArea = 0;
int top;
int areaWithTop;
int j = 0;  
while (j < s)  
{ 
if (stk.empty() || histArr[stk.peek()] <= histArr[j])  
stk.push(j++);  
else  
{  
top = stk.peek();
stk.pop();
areaWithTop = histArr[top] * (stk.empty() ? j : j - stk.peek() - 1);  
if (maxArea<areaWithTop)  
{  
maxArea = areaWithTop;  
}  
}  
} 
while (stk.empty() == false)  
{  
top = stk.peek();  
stk.pop();  
areaWithTop = histArr[top] * (stk.empty() ? j : j - stk.peek() - 1);  
  if (maxArea<areaWithTop)  
maxArea = areaWithTop;  
}  
  return maxArea;  
}  
public static void main(String[] args)  
{  
int[] histArr = {8, 9, 7, 6, 7, 3, 8};  
int s = histArr.length;
LargestRectArea2 obj = new LargestRectArea2();  
System.out.println("The maximum rectangular area is: " + obj.findMaxArea(histArr, s));  
}  
}   

 Output

The maximum rectangular area is: 30

Using Auxiliary Arrays

Another strategy is to use two auxiliary arrays to determine the previous smaller bar and the following smaller bar for each bar in the histogram. See the algorithm below.

Step 1: Initialize the two auxiliary arrays leftSmaller[] as well as rightSmaller[] with a negative sign and n, respectively.

Step 2: In the rightSmaller[] as well as leftSmaller[] arrays, we maintain the indexes of the subsequent and preceding smaller elements for each element, respectively. O(n) time is required.

Step 3: Using the jth bar, which is the smallest in the range remaining, we calculate the area for each bar.Smaller and to the right smaller[j] then multiplying it by the left-hand side difference Smaller and to the rightSmaller[j].

Step 4: By comparing the areas of each bar, the maximum area may be calculated. In step 3, the area for each of the several bars is calculated.

Example program

import java.util.Stack;  
public class LargestRectArea3  
{ 
public int findMaxArea(int a[], int s)  
{ 
Stack<Integer>stk = new Stack<>();  
stk.push(-1);  
int maxArea = a[0];  
int leftSmaller[] = new int[s];  
int rightSmaller[] = new int[s];  
for (int j = 0; j < s; j++)  
{  
leftSmaller[j] = -1;  
rightSmaller[j] = s;  
}  


int j = 0;  
while (j < s)  
{  
while(!stk.empty() &&stk.peek() != -1 && a[j] < a[stk.peek()] 
{ 
rightSmaller[stk.peek()] = (int)j;  
stk.pop();  
}  
if(j > 0 && a[j] == a[(j - 1)])  
{ 
leftSmaller[j] = leftSmaller[(int)(j - 1)];  
}  
else  
{ 
leftSmaller[j] = stk.peek();  
}  
stk.push(j);  
j = j + 1;  
}  




for(j = 0; j < s; j++)  
{ 
maxArea = Math.max(maxArea, a[j] * (rightSmaller[j] - leftSmaller[j] - 1));  
}  


return maxArea;  
}  
public static void main(String argvs[])  
{  
int[] histArr = {7, 2, 6, 5, 6, 2, 7};  
int size = histArr.length;


LargestRectArea3 obj = new LargestRectArea3();  
System.out.println("The maximum rectangular area is: " + obj.findMaxArea(histArr, size));  
}  
}   

Output

The maximum rectangular area is: 30

Analysis of the complexity

The final two methods have an O(n) time complexity, where n is the total amount of elements in the array.