aboutsummaryrefslogtreecommitdiff
path: root/brick_wall.py
diff options
context:
space:
mode:
Diffstat (limited to 'brick_wall.py')
-rw-r--r--brick_wall.py42
1 files changed, 42 insertions, 0 deletions
diff --git a/brick_wall.py b/brick_wall.py
new file mode 100644
index 0000000..1f7953c
--- /dev/null
+++ b/brick_wall.py
@@ -0,0 +1,42 @@
+# 554. Brick Wall
+
+"""
+there is a rectangular brick wall in front of you with 'n' rows of bricks.
+the i'throw has some number of bricks each of the same height (ie. one unit)
+butthey can be of different widths. the total width of each row is the same.
+draw a vertical line from the top to the bottom and cross the least bricks.
+if your line goes through the edge of a brick, then the brick is not
+considered as crossed. you cannot draw a line just along one of the two
+vertical edges of the wall, in which case the line will obviously cross no
+bricks. given the 2d array 'wall' that contains the information about the
+wall, return the minimum number of cross bricks after drawing such a vertical
+line
+"""
+
+
+class Solution(object):
+ def leastBricks(self, wall):
+ """
+ :type wall: List[List[int]]
+ :rtype: int
+ """
+ edge_freq = {}
+ max_freq = 0
+ for row in range(len(wall)):
+ edge_pos = 0
+ for brick_num in range(len(wall[row]) - 1):
+ curr = wall[row][brick_num]
+ edge_pos += curr
+ edge_freq[edge_pos] = edge_freq.get(edge_pos, 0) + 1
+ max_freq = max(edge_freq[edge_pos], max_freq)
+ return len(wall) - max_freq
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.leastBricks(
+ wall=[[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]]
+ )
+ )
+ print(obj.leastBricks(wall=[[1], [1], [1]]))