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: 3 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(int H[], int N);
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].
“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 Queue. 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.
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 array is a cuboid (rectangle), which looks like so; and just count the number of elements in the array. 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.
• 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 Queue. 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 array is: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 array is a cuboid (rectangle), which looks like so; and just count the number of elements in the array. 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.#include <stdio.h>The output is 7. Sounds like good news, but at app.codility.com/programmers, the result is:
int solution(int H[], int N) {
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)
{
int B[] = {8, 8, 5, 7, 9, 8, 7, 4, 8};
int N = sizeof(B)/sizeof(B[0]); //divide size of array by size of one (first) elements
int ret = solution(B, N);
printf("%i\n", ret);
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.
Yet Another Approach
The given array is:int B[] = {8, 8, 5, 7, 9, 8, 7, 4, 8};
The diagram is re-displayed just below, for easy reference by the reader.
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 array is:int B[] = {8, 8, 5, 7, 9, 8, 7, 4, 8};
The diagram is re-displayed just below, for easy reference by the reader.
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.
The C stack developed in the lesson for this task (problem) is used here. A program with the solution function is as follows (read through the code and comments). Pay particular attention to the solution function definition and to the user code in the main() function.
#include <stdio.h>The output is 7. Note that in the for-loop, the while-loop comes before the if-else construct. The expression, “stack.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 <stdlib.h>
struct Element {
int value;
struct Element *previous;
};
struct Stack {
int size;
struct Element *back;
int (*top)();
void (*push)(int);
void (*pop)();
} stack;
int top() {
if (stack.size > 0) //stack has at least 1 element
return stack.back->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from stack!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (stack.size == 0) { //first element
element->previous = 0;
stack.back = element;
stack.size = stack.size + 1; //add 1 to size
}
else {
element->previous = stack.back; //previous points to previous element
stack.back = element; //stack points to new element
stack.size = stack.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (stack.size > 0) { //stack has at least 1 element
struct Element *lastElement = stack.back;
stack.back = lastElement->previous; //point to previous element
free(lastElement); //free last (top) element from memory
stack.size = stack.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from stack!\n");
exit(1);
}
}
int solution(int H[], int N) {
int cnt = 0; //counter
for (int i = 0; i < N; i++) {
while (stack.size > 0 && H[i] < stack.top())
stack.pop();
if (stack.size > 0 && H[i] == stack.top()) {
continue; //do nothing
}
else {
stack.push(H[i]);
cnt++;
}
}
return cnt;
}
int main(int argc, char **argv)
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
int B[] = {8, 8, 5, 7, 9, 8, 7, 4, 8};
int N = sizeof(B)/sizeof(B[0]); //divide size of array by size of one (first) element
int ret = solution(B, N);
printf("%i\n", ret);
//user code begins
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.