2
\$\begingroup\$

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<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;
        }
    }
}
\$\endgroup\$
3
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 20, 2017 at 19:56
  • \$\begingroup\$ @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. \$\endgroup\$
    – Gilad
    Commented Jan 20, 2017 at 20:14
  • 1
    \$\begingroup\$ will now dig deeper \$\endgroup\$
    – Gilad
    Commented Jan 20, 2017 at 21:40

1 Answer 1

1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.