A StoneWall Solution in C++

StoneWall is an interesting problem that requires some brain cycles yet not too complex. It is good software engineer interview question.

Here is a C++ solution whose complexity is O(N).

#include <stack>

int solution(std::vector<int> &H) {
    int stones = 0;
    std::stack<int> heights;

    for (auto h: H) {
        while (!heights.empty() && h < heights.top()) {
            heights.pop();
        }
        if (heights.empty() || h > heights.top()) {
            heights.push(h);
            ++stones;
        }
    }
    return stones;
}

Analysis of the StoneWall problem

The key insight here (from the example and figure too) is that when a new wall of height h is added on the most right side, if it is the same height as the right most one among those walls on its left that are not taller than h, no need to use an additional stone for the wall. The stone for the wall of the same height on its left can be re-used for this wall.

Step by step analysis of the code

The data structure
During the walls are added one by one to the right, the taller ones than the latest one on the left one of the latest one need not to be checked again later. But the same height or shorter ones on the left should be considered still. So, this pattern is like “first in latest out”, right? A stack is suitable.

The algorithm
Now we have the key insight and the data structure of a heights stack, we can process the walls one by one.

For each wall, first remove/pop the walls on its left that is higher until the stack is empty or the wall is not higher than it. Then, compare the right most one (highest one) if there is at least one wall left in the stack. If the height is the same, continue to next wall. If the height of the highest one in the stack (the top) is smaller, add the new wall to the stack and count one more stone.

Complexity analysis

The for loop goes through each element once -> O(N) times where N is the size of the input H. Now let’s check the complexity for each element.

For each element, there is a while loop inside. But, for each element, it will be pushed at most once to the stack and popped at most once from the stack.

So overall, the complexity is O(N).