Codility - Stone Wall

Definitions:
$\mathbf{H} = \{x \in \mathbb{N}\ |1\leq x \leq 1,000,000,000\land |H| = N\},\mathbf{H}\, is\, a\, multiset.$
$\{N \in \mathbb{N}\ |\ 1\leq N \leq 100,000\}$

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.

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.

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:

Stone Wall

Python

# 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]

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

# 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)

Link to GitHub solution here .
Link to Codility problem here .