Counting Valleys

Question

I'm solving a question of Hackkerank, and I'm kinda stuck at this question. Since form end I have tried enough and somehow found the algorithm, but unfortunately it is not working out for most of the inputs. It is working for some test cases. Link is : Counting Valleys

Problem Statement

Here we have to count the number of valleys does XYZ person visits.

• A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

For One step up it U, and one step down it is D. We will be given the number of steps does XYZ person travelled plus the ups and down in the form of string, i.e, UUDDUDUDDUU like that.

Sample Input

8
UDDDUDUU

Sample Output

1

Explanation

If we represent _ as sea level, a step up as /, and a step down as \, Gary's hike can be drawn as:

_/\      _
   \    /
    \/\/

He enters and leaves one valley.

Algorithm

According to my theory :

The valley starts from going down :

• Traverse and check the two pairs from the string
• Check whether the obtained string is equals DD
• Again start a loop from the pos starting from DD, and find where the UU is falling or not
• Increase the count, break;
• Return count

But this algo fail for most of the test cases

Code

static int countingValleys(int n, String s) {
    int valleyVisits = 0, i=0;
    String str = "", strOne = "";

    /*Here we make pairs of two, in order to get the valley's visits. Since this visit starts from DD and ends at UU. So first we get the two strings and match with DD */
    while(i<n){
      //Gives the two strings from i to i+2
      str = s.substring(i, i+2);
      i = i+2; //not to start from next, but to the even pair

      //Checking if the pair starts from DD
      if(str.equals("DD")){
        int j = i;
        /* Rerunning the loop to get the end of the valley trip that is UU from this point */
        while(j < n){
          // Getting new strings starting after DD
          strOne = s.substring(j, j+2);
          j = j+2;

          //Similar operation, but the getting the end from DD and then breaks
          if(strOne.equals("UU")){
            valleyVisits++;
            break;
          }
        }
      }
    }

    return valleyVisits;
}

Passed Test Cases 1

8
UDDDUDUU

Expected Output : 1

Passed Test Case 2

12
DDUUDDUDUUUD

Expected Output : 2

Failed Test Case 1

10
DUDDDUUDUU

Expected Output : 2

Failed Test Case 2

100
DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD

Expected Output : 2

I'm there almost, but I don't know why my logic fails in here. Thanks in advance for any help. :)

Answer 1

The key to this problem is understanding what constitutes a valley. From my reading, you only count a valley when you come out of it. The rule states a valley ends with "... a step up to sea level".

So we keep track of our level and only if we move from just below sea level to sea level, do we count a valley. Here's my quick attempt:

private int countValleys(String s)
{
    int level = 0; // 0 is sea-level
    int valleys = 0;

    for (char c : s.toCharArray())
    {
        if (c == 'U') {
            level++;
            if (level == 0)
            {
                valleys++;
            }
        }
        else {
            level--;
        }
    }
    return valleys;
}

I ran the following test cases (from your question) and they all passed:

@Test
public void testValleyCounting()
{
    Assert.assertEquals(1, countValleys("UDDDUDUU"));
    Assert.assertEquals(2, countValleys("DDUUDDUDUUUD"));
    Assert.assertEquals(2, countValleys("DUDDDUUDUU"));
    Assert.assertEquals(2, countValleys("DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD"));
}

Please try on all the test cases you have and let me know if any fail.