Cover "Manhattan skyline" using the minimum number of rectangles

Question

I write to solve a Codility problem provided below,

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by an array H of N positive integers. 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.

Write a function:

class Solution { public int solution(int[] H); }

that, given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:

  H[0] = 8    H[1] = 8    H[2] = 5
  H[3] = 7    H[4] = 9    H[5] = 8
  H[6] = 7    H[7] = 4    H[8] = 8

the function should return 7. The figure shows one possible arrangement of seven blocks.

Assume that:

N is an integer within the range [1..100,000]; each element of array H is an integer within the range [1..1,000,000,000]. Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

I write a solution for the provided problem. The algorithm and code is provided below,

Algorithm

i. set block count = 1 and start iterating from the 2nd element of the array

ii. if the current depth is same as previous, keep going

iii. If the current depth is higher, push that in the stack and increase the count

iv. If the current depth is lower, keep poping till the current depth >= peek. Afterward, if the stack size = 0 or higher, increase the block count by 1

The code,

public static int solution(int[] H) {

    Stack<Integer> stack = new Stack<>();

    stack.push(H[0]);
    int count = 1;

    int N = H.length;

    for (int i = 1; i < N; i++) {

        if (H[i] == stack.peek()) {
            continue;
        } else if (H[i] > stack.peek()) {
            stack.push(H[i]);
            count++;
        } else {

            while (!stack.isEmpty() && H[i] < stack.peek()) {
                stack.pop();
            }

            stack.push(H[i]);
            count++;
        }
    }

    return count;
}

The solution doesn't provide the correct answer and I can't find the bug even after spending some time in debugging. Can anyone see that?

The test set is provided below and the answer is 7 (I get 8).

    int[] H = new int[9];

    H[0] = 8;
    H[1] = 8;
    H[2] = 5;
    H[3] = 7;
    H[4] = 9;
    H[5] = 8;
    H[6] = 7;
    H[7] = 4;
    H[8] = 8;

Thank you.

Answer 1

Python Solution

Here is my solution Solution with steps details

Codility python 100%

def solution(H):
"""
Codility 100%
https://app.codility.com/demo/results/trainingQKD6JP-PHA/

Idea is to use stack concept
Compute the minimum number of blocks needed to build the wall.
To build the wall start taking blocks of height one by one.
We need to take care of -
 - the blocked should not be used again
 - this is done only up to blocks height is greater than current
 - why we are using last 8 height block if there is already 8 height block used in previous step?
    reason is 8 is not present in stack top


8,
 8,----- can not use because on stack top 8 is already there
  5,
   7,
    9,
     8,
      7,------ can not use because on stack top 7 is already there
       4,
        8,

This is just example with height, see steps of output for details
 skip8           skip7
            |           |
|           |   |       |
|       |   |   |       |
|       |   |   |       |
|   |   |   |   |       |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |

Used blocks- 8 5 7 9 8 4 8

"""

block_count = 0
# stack is used to hold height used to building and remove all the blocks from it,
#  if any of the block of stack is greater than current block(to be added for building)
stack = []
for height in H:
    print(" ")
    print("Current Height " + str(height))
    print("Current stack " + str(stack))
    # Remove all blocks that are bigger than current height, stack should not be empty
    while stack and stack[-1] > height:
        stack.pop()
    print("After remove bigger blocks than current height " + str(stack))

    # stack is not empty and top item of stack is equal to current height
    if stack and stack[-1] == height:
        # Already used this size of block
        print("Already used this size of block " + str(height))
        continue
    else:
        # new block is required, push it's size to the stack
        block_count += 1
        stack.append(height)
        print("Add this block.... " + str(height) + " Minimum Blocks " + str(block_count))

return block_count

Answer 2

Another one in Java. Simpler, because I used assumption that height > 0.

    public int solution(int[] hs) {
        int squares = 0;
        Stack<Integer> s = new Stack<>();
        s.push(0);

        for (int h: hs) {
            while (s.peek() > h) {
                s.pop();
            }
            if (s.peek() != h) {
                s.push(h);
                ++squares;
            }
        }

        return squares;
    }

Answer 3

I find the bug and though it may be good to share. The reason is the new height is lesser than the peek value, we will keep popping the entities. So if the stack is not empty, the new height will be the same or higher than the stack peeks value.

If the new height will be the same, it means we already add a block for the height and will not add a new block. A condition is needed for the situation,

               if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

The code is provided below provides 100% score,

public int solution(int[] H) {

        Stack<Integer> stack = new Stack<>();

        stack.push(H[0]);
        int count = 1;

        int N = H.length;

        for (int i = 1; i < N; i++) {

            if (H[i] == stack.peek()) {
                continue;
            } else if (H[i] > stack.peek()) {
                stack.push(H[i]);
                count++;
            } else {

                while (!stack.isEmpty() && H[i] < stack.peek()) {
                    stack.pop();
                }

                /*
                 * the new entity is either in same elevation or higher
                 * */

                /*
                * if in same elevation, we already added the block, so keep iterating
                * */
                if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

                stack.push(H[i]);
                count++;
            }
        }

        return count;
    }

Answer 4

If someone is still interested in this exercise, I share my Python solution (100% in Codility)

def solution(H):
    stack, count = [], 1
    for i in H:
        if stack:
            if i == stack[-1]:
                continue
            if i < stack[-1]:
                while stack and stack[-1] > i:
                    stack.pop()
            if stack:
                if i > stack[-1]:
                    count+=1
                    stack.append(i)
            else:
                count+=1
                stack.append(i)
        else:
            stack.append(i)
    return count

Answer 5

Ruby 100%

def solution(h)
  h.inject([1, [h.first]]) do |(blocks, stack), n|
    next [blocks+1, stack.push(n)]    if stack.last < n
    stack.pop while stack.any? && stack.last > n
    next [blocks, stack] if stack.last == n

   [blocks+1, stack.push(n)]
  end.first
end