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