Brick Wall
- 1 min read
- Array
- LC-Medium
3 years ago
Solution
- Instead of thinking about drawing a line, look at the gaps.
- Count the number of gaps in each line, and count the total number of gaps seen PER LINE.
- PER LINE. That is important.
- At the end, take the maximum value for gaps seen so far, the number of bricks cut here would then be
num_rows - max_gaps
| Time | Space | Explanation |
|---|---|---|
O(n) | O(sum(wall[0])) or constant? |
def leastBricks(self, wall: List[List[int]]) -> int:
max_gaps, num_rows = 0, len(wall)
gaps_at_line = defaultdict(lambda: 0)
for r in range(num_rows):
line = 0
for i in range(len(wall[r]) - 1): # -1 to exclude last line, first line is automatically excluded
line += wall[r][i]
gaps_at_line[line] += 1
max_gaps = max(max_gaps, gaps_at_line[line])
return num_rows - max_gaps