Solution to Codility lesson5 Stone Wall problem, link to Codility problem and complete solution at the end of the post.
Definitions:
Context (from Codility):
You are going to build a stone wall. It should have different heights in different places. The height of the wall is specified by a zero-indexed array H. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall’s left end and H[N−1] is the height of the wall’s right end.
The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.
Problem:
Define a function solution with input H , such that solution returns the minimum number of blocks needed to build the wall.
- Expected worst-case time complexity is O(N);
- Expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Analysis:
To solve this problem we must visit every element of H. Each time that H[I + 1] is greater than H[I] we have to count a new block and we push H[I + 1] to the stack. For each new block we add it to the stack.
15 16 17 18 |
# If the height of the wall grows we have to use another block if H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 |
In the image below you can see that there is no way to use only one block,
If the height of the wall decreases we start searching for an element of the stack with the same height, so we don’t have to add a new block. If the stack is empty than this is the min height until here, and we have to add another block. If while looking for an element of the stack with the same height we found one that is smaller we must add a new block to the wall, because there is no way to keep using a block that has been used before.
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
# If H[k] is smaller than the current head keep looking if H[k] < height_stack.head(): while H[k] < height_stack.head(): height_stack.pop() # If the stack is empty we have to use a new block if height_stack.size == 0: height_stack.push(H[k]) result += 1 break # If H[k] is greater than the head there is no way to use a block so we have to use a new one elif H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 break # If H[k] is greater than the head there is no way to use a block so we have to use a new one elif H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 |
This is what we are looking for ,
![]() |
![]() |
But we could find something like this,
![]() |
![]() |
![]() |
Visiting every element of H gives us a time complexity of O(N).
In the worst case if H[I] is always lesser than H[I +1], we will put every element of H at the stack. Giving us a O(N) space complexity.
Complete Solution:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
# Name: StoneWall# Link: https://codility.com/demo/take-sample-test/stone_wall/ def solution(H): N = len(H) result = 0 lower = 0 height_stack = stack(N) height_stack.push(H[0]) result += 1 for k in xrange(1, N): # If the height of the wall grows we have to use another block if H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 # If the height of the wall decreases we have to check is there is a block with the same size as the required elif H[k] < height_stack.head(): height_stack.pop() # If H[k] is smaller than the current head keep looking if H[k] < height_stack.head(): while H[k] < height_stack.head(): height_stack.pop() # If the stack is empty we have to use a new block if height_stack.size == 0: height_stack.push(H[k]) result += 1 break # If H[k] is greater than the head there is no way to use a block so we have to use a new one elif H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 break # If H[k] is greater than the head there is no way to use a block so we have to use a new one elif H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 return result # Stack implementationclass stack(object): def __init__(self, N): self.size = 0 self._stack_ = [0] * N def push(self, x): self._stack_[self.size] = x self.size += 1 def pop(self): self.size -= 1 return self._stack_[self.size] def head(self): return self._stack_[self.size - 1]
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 59 60 61 62 |
# Name: StoneWall # Link: https://codility.com/demo/take-sample-test/stone_wall/ def solution(H): N = len(H) result = 0 lower = 0 height_stack = stack(N) height_stack.push(H[0]) result += 1 for k in xrange(1, N): # If the height of the wall grows we have to use another block if H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 # If the height of the wall decreases we have to check is there is a block with the same size as the required elif H[k] < height_stack.head(): height_stack.pop() # If H[k] is smaller than the current head keep looking if H[k] < height_stack.head(): while H[k] < height_stack.head(): height_stack.pop() # If the stack is empty we have to use a new block if height_stack.size == 0: height_stack.push(H[k]) result += 1 break # If H[k] is greater than the head there is no way to use a block so we have to use a new one elif H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 break # If H[k] is greater than the head there is no way to use a block so we have to use a new one elif H[k] > height_stack.head(): height_stack.push(H[k]) result += 1 return result # Stack implementation class stack(object): def __init__(self, N): self.size = 0 self._stack_ = [0] * N def push(self, x): self._stack_[self.size] = x self.size += 1 def pop(self): self.size -= 1 return self._stack_[self.size] def head(self): return self._stack_[self.size - 1] |
Time Complexity O(N)
Space Complexity O(N)
Hi, thanks for this article. I think there is a problem in your solution:
elif H[k] < height_stack.head():
height_stack.pop()
this can cause the stack to empty, but you fail to check if the stack is now empty while looking at the head below.