Question: https://codility.com/demo/take-sample-test/flood_depth/
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | from collections import namedtuple def solution(A): if len(A) < 3: return 0 # 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],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. continue elif height < stack[-1].height: stack.append(Block(height, 0)) else: 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: # C # 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: # C # 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) - \ stack[-1].height max_depth = max(max_depth, stack[-1].max_depth) + \ additional_depth stack.pop() # Combine leftward same-or-less-height blocks. These dropped # blocks are never going to be part of the remaining water # container. while len(stack) > 0 and height >= stack[-1].height: max_depth = max(max_depth, stack[-1].max_depth) stack.pop() stack.append(Block(height, max_depth)) overall_max_depth = 0 for block in stack: if block.max_depth > overall_max_depth: overall_max_depth = block.max_depth return overall_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?
My C++ Solution. O(N)