# StoneWall – Codility – Solution

Java solution to Codility StoneWall problem (Lesson 7 – Stacks and Queues) which scored 100%. The problem is to build a “Manhattan skyline” using the minimum number of rectangle blocks.

The strategy is:

• break up each array element into sub-blocks to store on a stack
• for each subsequent array element, check if there are existing blocks on the stack that can create it
• only add new block to the stack if impossible to reuse sub-blocks from stack

Example

{ 8, 8, 5, 7, 9, 8, 7, 4, 8 } will be broken down into the following 7 unique blocks:

(0,8) //8
(0,8) //8
(0,5) //5 (after clearing stack)
(0,5), (5,7) //7
(0,5), (5,7), (7,9) //9
(0,5), (5,7), (7,8) //8 (after popping stack)
(0,5), (5,7) //7 (after popping stack)
(0,4) // 4 (after clearing stack)
(0,4), (4,8) //8

```123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051package com.codility.lesson07.stacksqueues;

import java.util.Stack;

public class StoneWall {
public int solution(int[] H) {

//e.g. H = 2 would be a block of size (0, 2)
Block currentBlock = new Block(0, H);
Stack blockStack = new Stack();

int blocksRequired = 1;

for(int i=1; i<H.length; i++) { Block topStackBlock = blockStack.peek(); //remove any stack blocks that are taller than current block while(topStackBlock.upperHeight > H[i] ) {
blockStack.pop();
if(!blockStack.isEmpty()) {
topStackBlock = blockStack.peek();
}
else break;
}

if(blockStack.isEmpty()) {
blockStack.push(new Block(0, H[i]));
blocksRequired++;
}
else if(blockStack.peek().upperHeight - H[i] == 0) {
continue;
}
//put in a new block - need to calculate delta between tallest stack block and current block
else {
topStackBlock = blockStack.peek();
blockStack.push(new Block(blockStack.peek().upperHeight, H[i]));
blocksRequired++;
}
}

return blocksRequired;
}

class Block {
int lowerHeight;
int upperHeight;

Block(int pLowerHeight, int pUpperHeight) {
lowerHeight = pLowerHeight;
upperHeight = pUpperHeight;
}
}
}

```

TestNG test cases for this problem which all passed:

```12345678910111213141516171819202122232425262728293031323334353637383940package test.com.codility.lesson07.stacksqueues;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson07.stacksqueues.StoneWall;

public class StoneWallTests {
private StoneWall solution;

@BeforeTest
public void setUp() {
solution = new StoneWall();
}

@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { new int [] { 8, 8, 5, 7, 9, 8, 7, 4, 8 }, 7 },
new Object [] { new int [] { 8, 8, 5, 7, 9, 8, 7, 5, 8 }, 6 },
new Object [] { new int [] { 1, 2, 3, 4, 3 }, 4 },
new Object [] { new int [] { 8, 8, 5 }, 2 },
new Object [] { new int [] { 8, }, 1 },
new Object [] { new int [] { 8, 8 }, 1 },
new Object [] { new int [] { 8, 8, 8, 8, 8 }, 1 },
new Object [] { new int [] { 1000000000 }, 1 },
new Object [] { new int [] { 1000000000, 2 }, 2 },
new Object [] { new int [] { 2, 1000000000, 2 }, 2 },
new Object [] { new int [] { 2, 1000000000, 2, 1000000000 }, 3 },
new Object [] { new int [] { 2, 1000000000, 2, 1000000000, 1000000000 }, 3 },
};
}

@Test(dataProvider = "test1")
public void verifySolution(int[] pA, int pExpected) {
Assert.assertEquals(solution.solution(pA), pExpected);
}
}

```