Brick Wall Leetcode challenge I solved this problem on Leetcode


  There is a brick wall in front of you. The wall is rectangular and has
  several rows of bricks. The bricks have the same height but different
  width. You want to draw a vertical line from the top to the bottom and
  cross the least bricks.
  
  The brick wall is represented by a list of rows. Each row is a list of
  integers representing the width of each brick in this row from left to
  right.
  
  If your line go through the edge of a brick, then the brick is not
  considered as crossed. You need to find out how to draw the line to
  cross the least bricks and return the number of crossed bricks.
  
  You cannot draw a line just along one of the two vertical edges of the
  wall, in which case the line will obviously cross no bricks.

Input: 
[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]
Output: 2

  
  Explanation: 
  
  


The time complexity is O(height of the wall * total bricks in the wall) assuming Add, Remove, ContainsKey in Dictionary is O(1) and the space complexity is O(height of the wall). 

I'm not sure if there is a better algorithm or more suited data structure that could improve the performance. 

public int LeastBricksDictionary(IList&lt;IList&lt;int&gt;&gt; wall)
{
    var totalRows = wall.Count;
    var values = new SortedDictionary&lt;int, List&lt;Tuple&lt;int, int&gt;&gt;&gt;();
    int leastBrick = int.MaxValue, bricksNotCrossing = 0;
    for (int i = 0; i &lt; wall.Count; i++)
    {
        var newTuple = new Tuple&lt;int, int&gt;(i, 0);
        if (values.ContainsKey(wall[i][0]))
        {
            values[wall[i][0]].Add(newTuple);
        }
        else
        {
            values.Add(wall[i][0], new List&lt;Tuple&lt;int, int&gt;&gt;() { newTuple });
        }
    }
    while (values.Count &gt; 0)
    {
        int minSum = values.Keys.First();
        var minList = values[minSum];
        values.Remove(minSum);
        bricksNotCrossing = 0;
        foreach (var temp in minList)
        {
            int row = temp.Item1, col = temp.Item2;

            if (wall[row].Count &gt; 1 &amp;&amp; col + 1 &lt; wall[row].Count)
            {
                ++bricksNotCrossing;
            }
            if (col + 1 &lt; wall[row].Count)
            {
                int newSum = minSum + wall[row][col + 1];
                var newTuple = new Tuple&lt;int, int&gt;(row, col + 1);
                if (values.ContainsKey(newSum))
                {
                    values[newSum].Add(newTuple);
                }
                else
                {
                    values.Add(newSum, new List&lt;Tuple&lt;int, int&gt;&gt;() { newTuple });
                }
            }
        }
        leastBrick = Math.Min(leastBrick, totalRows - bricksNotCrossing);
    }
    return leastBrick;
}
You could look at it in a different way, transform the wall of bricks to a wall of edges, in your example it would be

1, 3, 5
3, 4
1, 4
2
3, 4
1, 4, 5


The first, the third and the last row have an edge at 1, thus you can draw a line that crosses three bricks less than the height of the wall.
You need to find the edge that appears the most.

In this case it would be four it appears in rows 2,3,5,6. 

After transforming the wall to a wall of edges, a SelectMany into a GroupBy and Max will do the trick.