Why my algorithm doesn't work for manhattan skyline from codility

139 Views Asked by At

I'm doing training tasks from codility. I am done with StoneWall with 100/100 rate but I'm stuck with the main idea of Manhattan skyline problem in that task. The task is described here https://app.codility.com/programmers/task/stone_wall/

Well when I read that problem the first time, i realized that I should just calculate minimum number of stone blocks to build the wall. There are no any explanations about how blocks can be extended and so on.(Probably assumptions include that I have to know it in advance. But I had never worked with such a problem). Based on my understanding of this problem I implemented the next algorithm(As it's turned out the incorrect one)

public int solution(final int[] H)
    {
        if (H.length == 1)
        {
            return 1;
        }

        int blocks = 0;
        int first = 0;
        for (int i = 1; i <= H.length; i++)
        {
            if (i == H.length || H[first] > H[i])
            {
                for (int k = first; k < i; k++)
                {
                    if (H[k] != 0)
                    {
                        for (int t = k + 1; t < i && H[k] <= H[t]; t++)
                        {
                            if (H[t] >= H[k])
                            {
                                H[t] = H[t] - H[k];
                            }
                            else
                            {
                                break;
                            }
                        }
                        blocks++;
                    }
                }
                first = i;
            }
        }
        return blocks;
    }

Above code works fine for simple little arrays. For example { 8, 8, 5, 7, 9, 8, 7, 4, 8 }. Obviously it failed performance. I wanted to run this to understand that i'm in correct way. But it returns incorrect results for e.g. large array with values within 1...20. The problem is that I don't understand the main idea of the building wall process so I cannot replicate it on my local.

Then I researched a little bit and found this solution on codility https://codility.com/media/train/solution-stone-wall.pdf It's saying that

The intuition is that by extending each stone block to the ground, we obtain a set of
buildings forming the given skyline.

I thought that it was a clue.(I should just stack smaller blocks on top of bigger ones.) But then I took a look at the figures with possible arrangements of blocks and it confused me again.

  1. https://app.codility.com/programmers/task/stone_wall/ 2. https://codility.com/media/train/solution-stone-wall.pdf

Finally I implemented it using the second picture above and it works good(100% on codility)

public int solution2(final int[] H)
    {
        if (H.length == 1)
        {
            return 1;
        }

        int blocks = 0;
        final ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(H[0]);

        for (int i = 1; i < H.length; i++)
        {

            while (stack.size() > 0 && stack.peek() > H[i])
            {
                stack.pop();
                blocks++;
            }
            if (stack.isEmpty() || stack.peek() < H[i])
            {
                stack.push(H[i]);
            }
        }

        return blocks + stack.size();
    }

Could someone explain me please why the first algorithm doesn't work for this task?

0

There are 0 best solutions below