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

[cc lang="java" escaped="true"]
package com.codility.lesson07.stacksqueues;

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;
		}
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package 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);
	}	
}
[/cc]