Brick Wall Leetcode challenge

Question

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<IList<int>> wall)
{
    var totalRows = wall.Count;
    var values = new SortedDictionary<int, List<Tuple<int, int>>>();
    int leastBrick = int.MaxValue, bricksNotCrossing = 0;
    for (int i = 0; i < wall.Count; i++)
    {
        var newTuple = new Tuple<int, int>(i, 0);
        if (values.ContainsKey(wall[i][0]))
        {
            values[wall[i][0]].Add(newTuple);
        }
        else
        {
            values.Add(wall[i][0], new List<Tuple<int, int>>() { newTuple });
        }
    }
    while (values.Count > 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 > 1 && col + 1 < wall[row].Count)
            {
                ++bricksNotCrossing;
            }
            if (col + 1 < wall[row].Count)
            {
                int newSum = minSum + wall[row][col + 1];
                var newTuple = new Tuple<int, int>(row, col + 1);
                if (values.ContainsKey(newSum))
                {
                    values[newSum].Add(newTuple);
                }
                else
                {
                    values.Add(newSum, new List<Tuple<int, int>>() { newTuple });
                }
            }
        }
        leastBrick = Math.Min(leastBrick, totalRows - bricksNotCrossing);
    }
    return leastBrick;
}

Answer 1

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.

Answer 2

I don't know whether you'd consider this a bug or not but consider a wall with zero bricks. Your code will output int.MaxValue for the least number of bricks crossed:

var wall = new List<IList<int>>();
var result = LeastBricksDictionary(wall); // int.MaxValue

I'd argue that you should output 0 in this case. I think omaraloraini has the right idea but I think it's probably easier to write a loop:

public int LeastBricksDictionary(IList<IList<int>> wall)
{
    var edgesPerColumn = new Dictionary<int, int>();
    var maxEdgesPerColumn = 0;
    // In the UK at least, a layer of bricks is called a course.
    foreach (var course in wall)
    {
        var columnIndex = 0;
        for (var i = 0; i < course.Count - 1; i++)
        {
            columnIndex += course[i];
            edgesPerColumn.TryGetValue(columnIndex, out int current);
            edgesPerColumn[columnIndex] = ++current;
            if (current > maxEdgesPerColumn)
            {
                maxEdgesPerColumn = current;
            }
        }
    }
    return wall.Count - maxEdgesPerColumn;
}

I just use a dictionary to keep a tally of the number of edges in each column and keep the current winner in a variable. My original code was simpler (only using the dictionary) but it failed the performance requirements on leetcode so I had to manually keep track of the maximum as well.