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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Stack;
public class StoneWall {
public int solution(int[] H) {
//e.g. H[0] = 2 would be a block of size (0, 2)
Block currentBlock = new Block(0, H[0]);
Stack blockStack = new Stack();
blockStack.add(currentBlock);
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++;
}
//block already exists in stack
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);
}
}