Codility ‘StoneWall’ Solution

Posted on by
Short Problem Definition:

Cover “Manhattan skyline” using the minimum number of rectangles.

Link

StoneWall

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

The explanation to this challenge has been posted on the Codility web, you can read it here.

Solution:
def solution(H):
    block_cnt = 0

    stack = []

    for height in H:
        # remove all blocks that are bigger than my height
        while len(stack) != 0 and stack[-1] > height:
            stack.pop()

        if len(stack) != 0 and stack[-1] == height:
            # we already paid for this size
            pass
        else:
            # new block is required, push it's size to the stack
            block_cnt += 1
            stack.append(height)

    return block_cnt



If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwitterredditpinterestlinkedin