Question Name: Flood-Depth or FloodDepth
This is a variant of Trapping Rain Water by LeetCode. The undergoing concept is the same. However, the implementation is a bit different.
Solution to Flood-Depth by codility
from collections import namedtuple
if len(A) < 3:
# The blocks in the stack is in strictly height descending order.
# For the first block in the stack, its max_depth is maximum water
# depth of its (exclusive) left area.
# The other blocks' max_depth is the maximum water depth between its
# previous block in the stack and itself, both exclusive.
Block = namedtuple("Block", ["height", "max_depth"])
stack = [Block(A,0)]
for height in A[1:]:
if height == stack[-1].height:
# These two adjacent blocks have the same height. They act
# totally the same in building any water container.
elif height < stack[-1].height:
max_depth = 0
# Let the current iterating block be C, the previous two
# blocks in the stack be A and B. And their positions are
# demoed as:
# A C
# A ... B ... C
# while the blocks between A and B are omitted. So do the
# blocks between B and C.
# The additional_depth consider the blocks A, B, and C only,
# and igonres all the omitted blocks, such as:
# A C
# A B C (no block is between A and B, or B and C)
# HOWEVER, the additional_depth is not always the maximum
# water depth between A and C, because there may be some
# water between A and B, or B and C, as exists in the omitted
# blocks. We need to adjust the additional_depth to get the
# maximum water depth between A and C, both exclusive.
while len(stack) > 1 and height > stack[-1].height:
additional_depth = min(stack[-2].height, height) - \
max_depth = max(max_depth, stack[-1].max_depth) + \
# Combine leftward same-or-less-height blocks. These dropped
# blocks are never going to be part of the remaining water
while len(stack) > 0 and height >= stack[-1].height:
max_depth = max(max_depth, stack[-1].max_depth)
overall_max_depth = 0
for block in stack:
if block.max_depth > overall_max_depth:
overall_max_depth = block.max_depth
I just want to point out that there is actually an O(N) time, O(1) space solution by using two pointers.
I think my solution concept is easy
Here is my solution and it passes all the tests. O(n) time complexity. And Simple!
Can you please explain why you take d = maxH – minH? Is d is accessable from other control flow statements?