# Largest Rectangle in a Histogram

Published: May 25, 2017

“Find the largest rectangular area in a histogram” is a famous algorithm problem using bars. There are some types of problems expressed by bars such as trapping water or skyline. Those look like similar since all are plotted on 2D plain multiple bars on. However, how to think and solve the problems are not the same. What data structure and algorithm can be applied to solve problems effectively is, sometime, confusing. For this reason, I’m going to add this topic to my memo.

#### Problem Description

Given an array of integers which denotes heights of each bar with a width 1, find the largest rectangluar area.

For example, the given array is [6, 2, 5, 4, 5, 1, 6], the largest will be 12 created from index 2 to 4.

```  .
6 . █           █
. █   █   █   █
. █   █ █ █   █
. █   █ █ █   █
. █ █ █ █ █   █
. █ █ █ █ █ █ █
0 . . . . . . . .
0           6

The largest area is from index 2 to 4.
.
6 . █           █
. █   █   █   █
+-----+
4 . █  |█ █ █|  █
. █  |█ █ █|  █
. █ █|█ █ █|  █
. █ █|█ █ █|█ █
0 . . . . . . . .
0   2   4   6
```

If the given array is [6, 2, 5, 4, 5, 2, 6] (only one different in the sixth element), the largest will be 14 from index 0 to 6.

```  .
6 . █           █
. █   █   █   █
. █   █ █ █   █
. █   █ █ █   █
. █ █ █ █ █ █ █
. █ █ █ █ █ █ █
0 . . . . . . . .
0           6

The largest area is from index 0 to 6.

.
6 . █           █
. █   █   █   █
. █   █ █ █   █
. █   █ █ █   █
+-------------+
.|█ █ █ █ █ █ █|
.|█ █ █ █ █ █ █|
0 . . . . . . . .
0           6
```

Easily we can think of exhaustive search O(n^2) solution by iterating all combinations. However, this often gets time out results at exhaustive testing.

#### The idea

This problem can be solved in a linear time using a stack. The stack saves indices which gives the highest so far. If histogram heights are 1, 2, and 3, the stack saves all three indices of 0, 1, 2.

Once it hits a lower height, a rectagular area will be calculated at that index. For the calculation, it needs the first no greater height seen so far compared to the current height. The information is saved in the stack. Since the stack saves indices of highest so far, popping out indices unitl the corresponding height is higher gives the target index.

The target index is the starting index of a subhistogram. With starting and current indices, the area will be calculated by multiplying width (difference of indices) and height. The ares is the result of the sub problem.

For example, after 3, if 1 comes in, the indices in the stack will be poped out. In the end, the stack will have the index 0 only whose height is 1.

Width (4) * Height (1) = 4

Repeating this process to the end of the given array, the maximum area can be found.

#### Java code

Below is the Java code based on the idea explained in the previous section.

The performance is: time O(n), space O(n).

The result is:

```12
14
```

#### Resources

Latest Posts

Setting Up GCP Instance for Deep Learning

This post is going to be very different from what I write here. The content is a memo how I create a GCP (Google Cloud Platform) instance for Deep Learning. While I study algorithm stuff, I also have been studying Deep Learning. In my early days, I tried to train my Deep Learning model only on a laptop. My laptop is 2012 model MacBook Pro, so I would say it is reasonably fast. However, when it comes to Deep Learning, the training was quite painful on the such machine. Often, I ran the training over night to get a disappointed result. Still, I didn’t use any of pricey cloud environment since it was my personal study unrelated to my day job. I wanted to save money.

Complete Binary Tree

Problems which ask a binary tree traverse, add/delete nodes, etc. are popular in algorithm questions. The binary trees are often just a binary tree or binary search tree. Sometimes, the problem pinpoints a particular type of a binary tree, for example, a balanced binary tree or complete binary tree.

Catalan number

What is Catalan number ? The Catalan number belongs to the domain of combinatorial mathematics. It is a sequence of natural numbers such that: `1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ...` The sequence appears in counting problems. Wikipedia has the details about the sequence: Catalan Number.