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

Suckow

I didn't bother reading the problem, but this part looks worrying to me for(int i = 1; i<H.length; i++), are you sure you didn't mean to say for(int i=0) ? – Espouse

i am sure. H[i] is compared to H[i-1]. H[0] is used to initialize some things above that. – Suckow

This is a LeetCode hard, and an "easy" example on Codility. I'd like to know what they are adding to their tea. – Corin

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.

Commie

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

Boltzmann

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.

Hutch

Finally I have enough points to be able to leave my feedback: what I would change in your code is the initial if block inside the for loop. Here is why: you are checking if the stack is empty at the end of the for loop, then at the beginning of the loop you are performing the the same check; so if at the end of the loop the stack is empty you will push an element on top of the stack and if it's not you will continue to the next iteration and go straight to the test. Either way that means that the stack will have at least one element at that point, thus making the initial test unnecessary. – Afghanistan

That test only makes sense if your stack is initially empty, but if you look at the requirements of the codility test it says that the array will certainly have at least one element, therefore you can safely push it to the top of the stack prior the beginning of the for loop. Sorry for the double comment: I was not allowed to put everything on a single comment – Afghanistan

Answer 4

Here is Scala version of @moxi code:

import scala.collection.mutable


object Solution {
    def solution(H: Array[Int]): Int = {

    val stack =  new mutable.Stack[Int]()

    var blockCounter :Int = 0

    for (i <- 0 to (H.length-1)) {

      var element = H(i)

      if (stack.isEmpty) {
        stack.push(element)
        blockCounter = blockCounter+1
      } else {
        while (!stack.isEmpty && stack.top > element) {
          stack.pop()
        }
        if (!stack.isEmpty && stack.top == element) {

        } else {
          stack.push(element)
          blockCounter = blockCounter+1
        }
      }
    }

    return blockCounter

  }
}

https://codility.com/demo/results/trainingM3BDSK-3YV/

Sallyanne

Answer 5

i got 100% you can find in this link

def solution(H):
   stack =[]

   count = 1

   stack.append(H[0])

   for i in range(1,len(H)):
       if len(stack) == 0:
          stack.append(H[i])
          count+=1
       if H[i] > stack[-1]:
          stack.append(H[i])
          count+=1
       while H[i] < stack[-1]:
          stack.pop()
          if len(stack) == 0:
              stack.append(H[i])
              count+=1
          elif H[i] > stack[-1]:
              stack.append(H[i])
              count+=1

   return count   

Inhospitality

Answer 6

This is my 100/100 Java solution.

public static int solution(int[] H) {
    // write your code in Java SE 8
    Stack<Integer> s = new Stack<Integer>();
    int count = 1;

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

Possible

Answer 7

Old question; hopefully it will still be useful. In your 3rd IF statement within the FOR loop you are not considering the case where H[i] == lowest.

Try this:

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

Also (but this is just a minor thing) the use of a variable to store the lowest is not necessary. By peeking and popping accordingly you can easily retrieve the lowest value from the stack. In addition you can make the code clearer and avoid comparing once with the head of on the stack, once with the lowest. Hope that makes sense. Here is my solution.

import java.util.Stack;
class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8
        Stack<Integer> sittingOn = new Stack<Integer>();
        sittingOn.push(H[0]);
        int counter = 1;
        for(int i = 1; i < H.length; i++){ 
            if(sittingOn.peek() < H[i]){
                counter++;
                sittingOn.push(H[i]);
            } 
            else{
                while (!sittingOn.isEmpty() && sittingOn.peek() > H[i]){
                    sittingOn.pop();
                }
                if (sittingOn.isEmpty() || sittingOn.peek() != H[i]){ 
                    sittingOn.push(H[i]);
                    counter++;
                }
            }
        }   
    }        
    return counter;
}

And here is the compact version of it I mentioned in my comment:

import java.util.Stack;
class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8
        Stack<Integer> sittingOn = new Stack<Integer>();
        sittingOn.push(H[0]);
        int counter = 1;
        for(int i = 1; i < H.length; i++){ 
            while (!sittingOn.isEmpty() && sittingOn.peek() > H[i]){
                sittingOn.pop();
            }
            if (sittingOn.isEmpty() || sittingOn.peek() != H[i]){ 
                sittingOn.push(H[i]);
                counter++;
            } 
        }   
    }        
    return counter;
}

Afghanistan

Worth noting that this solution would still work even after removing the first IF statement-block, (the second IF would cover that case as well), but it would be kind of slower as more (unnecessary) tests would be carried out. Moreover implementing the stack with a LinkedList rather than a Stack would make it more effiicient. – Afghanistan

Answer 8

I provide a solution for you in Java,

public int solution(int[] H) {

        Stack<Integer> stack = new Stack<>();

        stack.push(H[0]);
        int count = 1;

        int N = H.length;

        for (int i = 1; i < N; i++) {

            if (H[i] == stack.peek()) {
                continue;
            } else if (H[i] > stack.peek()) {
                stack.push(H[i]);
                count++;
            } else {

                while (!stack.isEmpty() && H[i] < stack.peek()) {
                    stack.pop();
                }

                /*
                 * the new entity is either in same elevation or higher
                 * */

                /*
                * if in same elevation, we already added the block, so keep iterating
                * */
                if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

                stack.push(H[i]);
                count++;
            }
        }

        return count;
    }

It scores 100% in the Codility testing.

Viv

Answer 9

Here is my C++ implementation using stack (codility reported 100% correctness and performance).

This logic does only horizontal blocking.

int solution(vector<int> &H) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> st;
    st.resize(H.size());
    int sp = -1;
    int c = 0;
    for (unsigned i = 0; i < H.size(); ++i) {
        int curElem = H.at(i);
        while (sp != -1) {
            if (curElem >= st[sp])
                break;
            sp--;
        }
        if (sp == -1 || curElem != st[sp]) {
            st[++sp] = curElem;
            c++;
        }
    }
    return c;
}

Trifacial

Answer 10

function solution(H) {
  let stack=[H[0]];
  let count=0;
  for(let i=1;i<H.length;i++){
    if(H[i]<stack[stack.length-1]){
     count=count+1;
     stack.pop();
     while(stack.length && stack[stack.length-1]>=H[i]){
        if(stack[stack.length-1]>H[i]){
          count=count+1;
          stack.pop();
        }else if(stack[stack.length-1]==H[i]){
          stack.pop();
        }
      }
    stack.push(H[i]);
    
    }else if(H[i]>stack[stack.length-1]){
    stack.push(H[i]);
   }

  }
 return count+stack.length;
}

Mckinleymckinney

This is my 100/100 JavaScript solution – Mckinleymckinney

Please edit your Answer to explain how the code answer the question, so that other people can take advantage of your knowledge. – Burdelle

Answer 11

A simple C# solution

 public int solution(int[] A) {
            int blocksCount = 0;
            List<int> previousLevels = new List<int>();
 
            for (int i = 0; i < A.Length; i++) {
                bool continuation = previousLevels.Contains(A[i]);
 
                previousLevels.RemoveAll(x => A[i] < x);
 
                if (!continuation) {
                    blocksCount++;
                    previousLevels.Add(A[i]);
                }
            }
            return blocksCount;
        }

Wilbertwilborn

Welcome to SO Osama. Your answer does not look related to the code in the question. – Exeter

Answer 12

Swift 100% solution:

public func solution(_ H : inout [Int]) -> Int {
    var stack = [Int]()
    var result = 0
outer:
    for element in H {
        func addElementAndIncrementResult() {
            stack.append(element)
            result += 1
        }

        if stack.isEmpty || element > stack.last! {
            addElementAndIncrementResult()
            continue
        }

        guard element != stack.last! else {
            continue
        }

        if element < stack.last! {
            while !stack.isEmpty {
                if stack.last! == element {
                    continue outer
                }
                if stack.last! > element {
                    stack.popLast()
                    continue
                }
                if stack.last! < element {
                    addElementAndIncrementResult()
                    continue outer
                }
            }

            stack.popLast()
            addElementAndIncrementResult()
            continue
        }
    }
    return result
}

Divebomb