## Brute Force way

My first idea was to go through each column of the whole wall, but it would lead to TLE, since the length of a brick could be very huge:

```
class Solution(object):
def leastBricks(self, wall):
least = len(wall)
while wall[0] and not (wall[0][0] == 1 and len(wall[0]) == 1):
count = 0
for row in wall:
if row[0] == 1:
row.pop(0)
else:
row[0] -= 1
count += 1
least = min(least, count)
return least
```

## Using hashtable

Then I realized I only needed to count the occurrence of each brick space and used the height of wall to subtract the max occurrence of the space

```
class Solution(object):
def leastBricks(self, wall):
spaceMap = dict()
for row in wall:
spacelen = 0
for brick in row[:-1]: # avoid counting wall edge
spacelen += brick
if spacelen not in spaceMap:
spaceMap[spacelen] = 1
else:
spaceMap[spacelen] += 1
least = len(wall) - max(spaceMap.values())
return least
```

Time Complexity: O(n), n for number of bricks

Space Complexity: O(n)