javaalgorithm# manhattan skyline cover failing some test cases

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

Solution

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.

- Replacement for the deprecated URL(URL context, String spec) constructor that also works with older Java versions
- How to use WebClient to execute synchronous request?
- SpringBoot 2 the elements were left unbound
- Manually converting a string to an integer in Java
- Java is asking to return a value even when the value is returned in the if-else ladder
- Bounded PriorityBlockingQueue
- HSEARCH000151: Unable to get input stream from object of type byte
- How to get a resources path after jlink-ing?
- Error - trustAnchors parameter must be non-empty
- Build WHERE clause dynamically based on filter in queryDSL
- Best practice to select data using Spring JdbcTemplate
- Doubling each letter in a String
- To find the next work day
- Create advanced search in JPA through user defined dynamic where clause conditions
- Flink task manager does not unload classes
- Implicit casts in Java (passing value type wrappers to methods expecting a regular Integer or Long)
- How do I send an e-mail in Java?
- In Java Failing to invoke method with parameters even though seems to match the getMethod() call
- SQL server hanged suddenly - all DB connections are active but no response - SQL server 2016
- In Java how to synchronize cache read and write operations
- Unable to connect to the remote Cassandra datacenter with the options provided in error
- Creating a hierarchy of Java subclasses
- how to return a list of employee's names with the highest pay rate in java
- "Unsupported class file error" on a Vaadin 14 project
- Does Spring @Transactional attribute work on a private method?
- How to create a BKS (BouncyCastle) format Java Keystore that contains a client certificate chain
- Prevent Kafka Streams Consumer from writing offsets / wait for one stream to consume all records before starting the second stream
- Why does my SQL while(set.next()) skips the first element?
- Combine multiple lists in Java
- How to map from Page<ObjectOne> to Page<ObjectTwo> in Spring Data 2?