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

1
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
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;
    }
  }
}

TestNG test cases for this problem which all passed:

1
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
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);
  }
}