Problem of the day: Largest rectangle in a histogram

Problem of the day for today is Largest rectangle in a histogram: Given n non-negative integers representing the histogram’s bar heights where the width of each bar is 1, find the area of largest rectangle in the histogram.

largest-rectangle-in-histogram

In this example, we are given 7 heights [6, 2, 5, 4, 5, 1, 6] and can see that the area of the largest rectangle is 3*4 = 12.

Continue reading

Advertisements

Using generators for on-demand tree traversal

Let’s take a short break from the ongoing series of posts on AI to look at an interesting problem and a useful accompanying concept.

Problem: Given a BST and a value k, find two elements in the BST which sum to k.

Continue reading