554. Brick Wall

Time: O(n*k)

Space: O(n)

Intuition

Find the vertical line that crosses the fewest bricks (most edges). Count edge positions using a hashmap, find max edge count, answer = rows - maxEdges.

Algorithm

1For each row, compute cumulative widths (except last brick).
2Increment edge count for each cumulative position.
3Find max edge count.
4Return totalRows - maxEdgeCount.

Common Pitfalls

•Don't count the outer edges (start of row and end of row are not valid crossing points).

554.cs

// Approach: Count crack frequencies (prefix sums of brick widths) per row;
// the fewest crossings = rows − max crack frequency.
// Time: O(n*k) Space: O(n)

public class Solution
{
    public int LeastBricks(IList<IList<int>> wall)
    {
        int maxFreq = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();

        foreach (var row in wall)
        {
            int prefix = 0;
            for (int i = 0; i < row.Count - 1; ++i)
            {
                prefix += row[i];
                if (count.ContainsKey(prefix))
                    count[prefix]++;
                else
                    count[prefix] = 1;
                    
                maxFreq = Math.Max(maxFreq, count[prefix]);
            }
        }

        return wall.Count - maxFreq;
    }
}

Was this solution helpful?