Solution to Codility lesson5 Stone Wall problem, link to Codility problem and complete solution at the end of the post.

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,

H[I] < H[I + 1]
H[I] < H[I + 1]

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 ,

H[I] == H[I - K] , for K > 0
H[I] == H[I – K] , for K > 0
H[I] == H[I - K], for K > 0
H[I] == H[I – K], for K > 0

 

But we could find something like this,

H[I] is the min height until now
H[I] is the min height until now
H[I] > H[I -K], for K > 0
H[I] > H[I -K], for K > 0
H[I] > H[I -K], for K > 0
H[I] > H[I -K], for K > 0

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:

Time Complexity O(N)
Space Complexity O(N)

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

One thought on “Codility – Stone Wall

  1. 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.

/*Comment here*/