manhattan skyline cover failing some test cases

Question

I am doing exercises on codility. I have spent two days on this problem with no improvement in my score. I get 100% on my correctness score, but fail some performance tests because it returns the wrong answer (not because of time or space complexity). My wrong results are always less than the expected answer. Can anyone think of a case where I need to add a stone that I am missing?

This is the prompt:

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by a zero-indexed array H of N positive integers.

H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.

Write a function that, given a zero-indexed array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

class Solution { public int solution(int[] H); }

For example, given array H containing N = 9 integers:

  H[0] = 8    H[1] = 8    H[2] = 5    
  H[3] = 7    H[4] = 9    H[5] = 8    
  H[6] = 7    H[7] = 4    H[8] = 8    

The function should return 7. The figure shows one possible arrangement of seven blocks.

Assume that:

• N is an integer within the range [1..100,000];
• Each element of array H is an integer within the range [1..1,000,000,000].

Complexity:

• Expected worst-case time complexity is \$O(N)\$;
• Expected worst-case space complexity is \$O(N)\$, beyond input storage (not counting the storage required for input arguments).
• Elements of input arrays can be modified.

This is my solution:

 import java.util.*;

class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8

        LinkedList<Integer> stack = new LinkedList<Integer>();
        int count = 1;
        int lowest = H[0];
        stack.push(H[0]);

        if(H.length == 1){
            return 1;   
        }
        else{
        for(int i = 1; i<H.length; i++){
            if(H[i] > H[i-1]){
                stack.push(H[i]);
                count++;   
            }
            if(H[i] < lowest){
                while(stack.size() > 0){
                    stack.pop();   
                }
                stack.push(H[i]);
                lowest = H[i];   
                count++;
            }
            if(H[i] < H[i-1] && H[i] > lowest){
                while(stack.size() > 0 && stack.peek() > H[i]){
                    stack.pop();   
                }
                if(stack.size() > 0 && stack.peek() < H[i]){
                    stack.push(H[i]);
                    count++;   
                }
            }
        }
        }

        return count;
    }
}

Answer 1

One possible problem that can be spotted is the Linkedlist is not properly managed when H[i]==lowest. When H[i]==lowest, the program should reset the Linkedlist with one lowest block only. Simply correct the second if-block as:

if(H[i] <= lowest){
    while(stack.size() > 0){
        stack.pop();   
    }
    stack.push(H[i]);                
    if (H[i]!=lowest)
    {
        lowest = H[i];
        count++;
    }
}

Consider case H = {1,4,3,4,1,4,3,4,1}. The correct output is 7 while your code return 6.

The problem appears when i is 6. The while-loop in third if-block reset stack to {3,1} which leads to stack.peek() < H[i] in coming if-block failure (stack.peek() = H[6] = 3).

Additionally, the three if-block can be rewrite as if-else-if-else-if block since value of H[i] can meet one of the three condition only for any i.

Answer 2

import java.util.*;

class Solution {
    public int solution(int[] H) {
        Stack<Integer> stack = new Stack<Integer>();
        int count = 1;

        stack.push(H[0]);

        for (int i = 1; i < H.length; i++) {
            if (stack.empty()) {
                stack.push(H[i]);
                count++;
            }
            if (H[i] > stack.peek()) {
                stack.push(H[i]);
                count++;
            }
            while (H[i] < stack.peek()) {
                stack.pop();
                if (stack.empty()) {
                    stack.push(H[i]);
                    count++;
                } else if (H[i] > stack.peek()) {
                    stack.push(H[i]);
                    count++;
                }
            }
        }
        return count;    
    }
}

Answer 3

I'm going to add another Java Solution 100/100, I added my own Stack class.

https://codility.com/demo/results/demoX7Z9X3-HSB/

Here's the code:

import java.util.ArrayList;
import java.util.List;

public class StoneWall {

      public int solution(int[] H) {
          int len = H.length;
          Stack<Integer> stack = new Stack<>(len);
          int blockCounter = 0;

          for (int i = 0; i < len; ++i) {
              int element = H[i];
              if (stack.isEmpty()) {
                  stack.push(element);
                  ++blockCounter;
              } else {
                  while (!stack.isEmpty() && stack.peek() > element) {
                      stack.pop();
                  } 
                  if (!stack.isEmpty() && stack.peek() == element) {
                     continue;
                  } else {
                      stack.push(element);
                      ++blockCounter;
                  }
              }
          }

          return blockCounter;
      }

      public static class Stack<T> {
          public List<T> stack;

          public Stack(int capacity) {
              stack = new ArrayList<>(capacity);
          }

          public void push(T item) {
              stack.add(item);
          }

          public T pop() {
              T item = peek();
              stack.remove(stack.size() - 1);
              return item;
          }

          public T peek() {
              int position = stack.size();
              T item = stack.get(position - 1);
              return item;
          }

          public boolean isEmpty() {
              return stack.isEmpty();
          }
      }
  }

Any feedback will be appreciated.