# Find the biggest rectangle in a bar graph

Find the largest rectangle area on a bar graph. Example: if you had a graph of 1,4,5,3,3,5 the answer would be 15 (3x5) which is formed by the rectangle that is 3 high and spans from position 2 (1 based) to 6.

Please review my answer and comment about runtime complexity, memory usage, and basically anything else you think I need to improve if this was a job interview for your company.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Interviews
{
class Program
{
static void Main(string[] args)
{
List<int> barGraph = new List<int>() { 1, 4, 5, 3, 3, 5 };
int max = GetBiggestRectSize(barGraph);
//should output 15
barGraph = new List<int>() { 1, 4, 2, 3, 3, 5 };
max = GetBiggestRectSize(barGraph);
//should output 10
}

private static int GetBiggestRectSize(List<int> barGraph)
{
int maxRectSize = 0;
int max = barGraph.Max();
for (int i = 1; i <= max; i++)
{
int tempSize = 0;
for (int j = 0; j < barGraph.Count; j++)
{
if (barGraph[j] >= i)
{
tempSize += i;
}
else
{
if (tempSize > maxRectSize)
{
maxRectSize = tempSize;
}
tempSize = 0;
}
if (tempSize > maxRectSize)
{
maxRectSize = tempSize;
}
}
}
return maxRectSize;
}
}
}

• The code seems correct but very inefficient. You need to come up with some smarter algorithm to solve it. This is a pretty well-known problem, I know of two approaches, one using a stack and the other using disjoint set union. Commented Jan 20, 2017 at 19:56
• @RazimanT.V. thanks very much for the comment, geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1, I will not dig deeper into this. Commented Jan 20, 2017 at 20:14
• will now dig deeper Commented Jan 20, 2017 at 21:40

As others have pointed out, your algorithm is very inefficient. Especially if the size of the columns vary widely:

int[] columns = { 1, 5, 40000, 3 } // Just to make my point clear :-)


This will cause your algorithm to check 39996 numbers (= column heights) for no reason.

So a minor change in your code could make it a lot more efficient, although it isn't still a very efficient approach:

private int GetBiggestRectSize(List<int> barGraph)
{
int maxRectSize = 0;
//int max = barGraph.Max();

// CHANGE: Instead of checking all values from max to 1 - only check values in the input graph.
foreach (int i in barGraph)
{
int tempSize = 0;
for (int j = 0; j < barGraph.Count; j++)
{
if (barGraph[j] >= i)
{
tempSize += i;
}
else
{
if (tempSize > maxRectSize)
{
maxRectSize = tempSize;
}
tempSize = 0;
}
if (tempSize > maxRectSize)
{
maxRectSize = tempSize;
}
}
}

return maxRectSize;
}