1
\$\begingroup\$

Here is the task description for the codility's stonewall problem. I would like to get a feedback on my code, and I specify at the bottom what the title states. (I had to make the figure by hand, because I couldn't paste the site's one for some reason, but it can be seen here, if mine doesn't look right)

Task description


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:

class Solution { public int solution(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 shows one possible arrangement of seven blocks.

enter image description here

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].

And here is my 100% O(N) time complexity solution. As the title says, I find it kinda weird that different paths do the same thing. Should I fix that? if so... how? the logic is correct. And should I care? Thinking in bigger problems, if many paths do the same thing, and requirements change, I should change code in many places, which is not recommended.

using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    public int solution(int[] H) {
        Stack<int> heightsStack = new Stack<int>();
        int blocksCounter = 0;

        for (int height = 0; height < H.Length; height++)
        {
            if (heightsStack.Count > 0)
            {
                while (heightsStack.Count > 0 && heightsStack.Peek() > H[height])
                {
                    heightsStack.Pop();
                }
                if (heightsStack.Count > 0)
                {
                    if (heightsStack.Peek() < H[height])
                    {
                        blocksCounter++;
                        heightsStack.Push(H[height]);
                    }
                }
                else
                {
                    blocksCounter++;
                    heightsStack.Push(H[height]);
                }
            }
            else
            {
                blocksCounter++;
                heightsStack.Push(H[height]);
            }
        }
        return blocksCounter;
    }
}
\$\endgroup\$
1
\$\begingroup\$

Some of these branches can be eliminated. Let's see:

if (heightsStack.Count > 0)
{
  if (heightsStack.Peek() < H[height])
  {
    blocksCounter++;
    heightsStack.Push(H[height]);
  }
}
else
{
  blocksCounter++;
  heightsStack.Push(H[height]);
}

Here, there are two conditions where we execute the two common lines: heightsStack.Count <= 0 or heightsStack.Peek() < H[height]. Since Count can't be negative, let's rewrite it as such:

if (heightsStack.Count == 0 || heightsStack.Peek() < H[height])
{
  blocksCounter++;
  heightsStack.Push(H[height]);
}

if (heightsStack.Count > 0)
{
  while (heightsStack.Count > 0 && heightsStack.Peek() > H[height])
  {

The first if-statement is redundant. If heightStack.Count > 0 is false, the while statement will be false as well. We would immediately fall through and end up at the if-statement in the section above. This if-statement would evaluate to true, since heightStack.Count == 0 still. And it would execute the two common lines.

This would leave the body of the for-loop as follows:

while (heightsStack.Count > 0 && heightsStack.Peek() > H[height])
{
  heightsStack.Pop();
}
if (heightsStack.Count == 0 || heightsStack.Peek() < H[height])
{
  blocksCounter++;
  heightsStack.Push(H[height]);
}

Note, that we only have one branch with the two common lines.


There's one last thing. You're using a for-loop, and only using the looped variable to index directly. Instead, consider using a foreach loop:

public int solution(int[] H)
{
  Stack<int> heightsStack = new Stack<int>();
  int blocksCounter = 0;

  foreach(int height in H)
  {
    while (heightsStack.Count > 0 && heightsStack.Peek() > height)
    {
      heightsStack.Pop();
    }
    if (heightsStack.Count == 0 || heightsStack.Peek() < height)
    {
      blocksCounter++;
      heightsStack.Push(height);
    }
  }
  return blocksCounter;
}

As far as algorithm goes, you do what I would have come up with, so I have nothing more to say about that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.