554.brick-wall.md

554. Brick Wall

Hash Table

For the input wall:

wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

0, 1, 2, 3, 4, 5, 6
|--|-----|-----|--|
|--------|--|-----|
|--|--------|-----|
|-----|-----------|
|--------|--|-----|
|--|--------|--|--|

To find the minimum number of crossed bricks, we can find the maximum number of edge position that are not crossed. We can use a hash table to store the number of edges at each position.

1, 2, 3, 4, 5, 6
O     O     O  O
      O  O     O
O        O     O
   O           O
      O  O     O
O        O  O  O
3  1  3  4  2  X
         *       
         // The maximum number of edges that are not crossed is 4, answer is 6 - 4 = 2

fun leastBricks(walls: List<List<Int>>): Int {
    val countMap = HashMap<Int, Int>()
    var max = 0
    for (wall in walls) {
        var sum = 0
        for (i in 0 until wall.size - 1) {
            sum += wall[i]
            val count = (countMap[sum] ?: 0) + 1
            max = maxOf(max, count)
            countMap[sum] = count
        }
    }
    // Or we can use `countMap.maxByOrNull { it.value }?.value ?: 0` to find the max value in the map.
    return walls.size - max
}