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;
using System.Threading.Tasks;

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

        private static int GetBiggestRectSize(List&lt;int&gt; barGraph)
        {
            int maxRectSize = 0;
            int max = barGraph.Max();
            for (int i = 1; i &lt;= max; i++)
            {
                int tempSize = 0;
                for (int j = 0; j &lt; barGraph.Count; j++)
                {
                    if (barGraph[j] &gt;= i)
                    {
                        tempSize += i;
                    }
                    else
                    {
                        if (tempSize &gt; maxRectSize)
                        {
                            maxRectSize = tempSize;
                        }
                        tempSize = 0;
                    }
                    if (tempSize &gt; maxRectSize)
                    {
                        maxRectSize = tempSize;
                    }
                }
            }
            return maxRectSize;
        }
    }
}
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&lt;int&gt; 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 &lt; barGraph.Count; j++)
    {
      if (barGraph[j] &gt;= i)
      {
        tempSize += i;
      }
      else
      {
        if (tempSize &gt; maxRectSize)
        {
          maxRectSize = tempSize;
        }
        tempSize = 0;
      }
      if (tempSize &gt; maxRectSize)
      {
        maxRectSize = tempSize;
      }
    }
  }

  return maxRectSize;
}