### View *Brick Wall* on LeetCode

## Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(n * m) - The algorithm traverses through every element, resulting in the O(n * m) time complexity.

**Space Complexity**

O(n * m) - In the worst case, there are no gaps with a frequency greater than one resulting in the dictionary containing about n * m elements.

**Runtime Beats**

81.85% of other submissions

## Explanation

The algorithm records the frequency of a gap at a certain number in the `count_gap`

dictionary and subtracts that from the length of the wall (the total amount of layers).

The algorithm calculates the gaps by taking the sum of the current brick and its previous bricks; it then increments the frequency of this gap in the dictionary. The algorithm avoids summing the last element of each row because that would result in an incorrect output since the last element of each row will always sum to the same number due to it being the endpoint of the brick wall.

Once the algorithm records all the gaps, it subtracts the gap with the highest frequency from the total amount of layers resulting in the least amount of bricks to go through.

## Data Structure Used

**Hash Map (Dictionary) -** A data structure that maps keys to their values. Each key may only appear once.

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
def leastBricks(self, wall: List[List[int]]) -> int:
count_gap = {0 : 0}
for row in wall:
total = 0
for brick in row[:-1]:
total += brick
count_gap[total] = 1 + count_gap.get(total, 0)
return len(wall) - max(count_gap.values())