StoneWall at app.codility.com/programmers in C++ Explained: Cover "Manhattan skyline" using the minimum number of rectangles.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 7 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 4 Jul 2025
Problem
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 an 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:
int solution(vector<int> &H);
that, given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.
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.
Write an efficient algorithm for the following assumptions:
• 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].
Note:
In the expression, “H[I]” in the problem, I is uppercase i and not lowercase el (l).“H[I] is the height of the wall from I to I+1” means H[I] is the height of the wall from the vertical line of index I to the vertical line of index I+1 (i plus 1).
The lesson (tutorial) for this problem is on Stack and Queues. So it should occur to the candidate that stack or queue is used. Actually it is the stack that is used. This means that for all the four tests (problems) of this lesson, only stack has been used and the queue has not been used.
Wrong Brute Force Approach
The given vector is:vector<int> B{8, 8, 5, 7, 9, 8, 7, 4, 8};
A possible brute force approach is to assume that each value in the given vector is a cuboid (rectangle), which looks like so; and just count the number of elements in the vector. With that the number of cuboids will be 9. Now, 9 is close to 7, but it is not accepted as minimum number of blocks by app.codility.com/programmers. Also, the stack or queue has not been used. Still, B[0] and B[1] likely form one block.
Another Approach
The diagram is re-displayed just below, for easy reference by the reader.
With the given data, the third block, B[3] of height 7, should not be counted twice. Looking at the diagram: the number of heights after the first is 7. These are the number of changes in height. Hoping that for other test cases at app.codility.com/programmers, counting the number of changes (heights after the first) will work, the program is (read through the code and comments):
#include <iostream>The output is 7. Sounds like good news, but at app.codility.com/programmers, the result is:
#include<vector>
using namespace std;
int solution(vector<int> &H) {
int N = H.size();
int cnt = 0; //counter
for (int i = 1; i < N; i++) { //counting beginnings after 0, in order to count changes
if (H[i] != H[i-1]) {
cnt++;
}
}
return cnt;
}
int main(int argc, char **argv)
{
vector<int> B{8, 8, 5, 7, 9, 8, 7, 4, 8};
int ret = solution(B);
cout << ret << endl;
return 0;
}
Task score : 7% - Correctness : 20% ; Performance : 0%
Detected time complexity : Not even given (not even quoted)!
This is embarrassing! The diagram is re-displayed just below, for easy reference by the reader.
Observe that if the second block extended just by one index to the right, and the last index being at 9 = (10 – 1), then the above solution() function would have returned 8 and not 7. The above solution() function is quit flawed. It still did not use a stack.
Yet Another Approach
The given vector is:vector<int> B{8, 8, 5, 7, 9, 8, 7, 4, 8};
The diagram is re-displayed just below, for easy reference by the reader.
Observe that in the diagram, the first block takes index 0 and 1. The second block takes index 2, 3, 4, 5, and 6. There are other blocks on top of the second block, which must be counted.
A candidate may decide to count the changes as the wall is scanned with the eye from left to right. If that is done, 8 will result as the number of blocks, because the height 7 will be counted two times. Though 8 is nearer to 7 than 9, app.codility.com/programmers still does not accept 8 as the minimum number of blocks, for this example data.
A way has to be looked for, using the stack, so that no block is counted twice.
Smart Approach
The given vector is:vector<int> B{8, 8, 5, 7, 9, 8, 7, 4, 8};
The diagram is re-displayed just below, for easy reference by the reader.
Observe that in the diagram, the first block takes index 0 and 1. The second block takes index 2, 3, 4, 5, and 6. On top of this second block are other blocks. The third block is on top of this second block. The third block takes index 3, 4, 5, and 6. On top of this third block, are two other blocks. A way has to be looked for, using the stack, so that no block is counted two times.
Notice that from the bottom of the diagram, a block will extend as far as possible, to the right, from the left. Also notice that a spread block may be counted twice when the wall descends. The third block from index 3 to 6 (inclusive), may be counted the second time, at index 6.
The solution is as follows:
Scan the given array, index by index. When there is a new height (a change) for the next index, higher than the height of the previous index (beginning with 0), the new higher height is pushed onto the stack and counted. If there is no change in height from the next index, nothing is pushed onto the stack and there is no counting.
If the new height is lower than the previous height, at the next index, all the heights from the top of the stack, going downwards, are removed from the stack (popped off) until the new height is either equal to or less than what is encountered next at the top of the stack. That removal is done in a while-loop. If the new height is equal to what is encountered next at the top of the stack, then there is no pushing of the new height onto the stack, and there is no counting. If the new height is less than what is encountered next at the top of the stack, then a new block starts. That new height is pushed onto the stack and the counter incremented. The very last height of 0 at the end of the wall is naturally ignored.
#include <iostream>The output is 7. Note that in the for-loop, the while-loop comes before the if-else construct. The expression, “s.size() > 0” is to prevent access to the stack, when it is empty, and so prevent the issue of the annoying out-of-bounds error message (“Segmentation fault (core dumped)” error).
#include<stack>
#include<vector>
using namespace std;
int solution(vector<int> &H) {
stack<int> s;
int N = H.size();
int cnt = 0; //counter
for (int i = 0; i < N; i++) {
while (s.size() > 0 && H[i] < s.top())
s.pop();
if (s.size() > 0 && H[i] == s.top()) {
continue; //do nothing
}
else {
s.push(H[i]);
cnt++;
}
}
return cnt;
}
int main(int argc, char **argv)
{
vector<int> B{8, 8, 5, 7, 9, 8, 7, 4, 8};
int ret = solution(B);
cout << ret << endl;
return 0;
}
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
The scanning of the given array is done by a for-loop. The body of the for-loop begins with a while loop that on descending of the wall, removes any block in the stack that is higher than the new level. This is done continuously while still at the new level. The body of the for-loop does not start with pushing a block into the top of the stack and counting.
Next in the body, is an if/else statement. The if-part skips the index of the for-loop if the previous level of the wall is the same as the current new level (current for-loop index) of the wall. Note that the if-part does not do the pushing of a block into the top of the stack and count. This is done by the else-part, when there is assurance that neither a spread block is being counted twice, nor the wall is maintained at the same level.
Thanks for reading.