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. :)

Drinker

I think you're over complicating it. Simply keep track of your current level (starting at sea level). If you drop below sea level and come back up, that's a valley. Nothing else matters. – Contraband

I tried, but still couldn't get the result. I have put up a check too if (s.charAt(i) == 'U'){level++ if(level==0) valeys++;}, else if(s.charAt(i) == 'D'){level--; if(level==0) valleys++;}. But got the wrong result – Drinker

That looks better, but is still not quite right. Check out my answer. – Contraband

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.

Contraband

Thanks for the edit, but question remains same for the next one that is : And why can't we check the level in both the cases, since the level=0 can come in any one of the cases – Drinker

I was checking level == -1 before I incremented the level. I've switched to incrementing first and checking level == 0 for clarity. – Contraband

There's no need to check anything when moving down as it's only a valley if you come out of it. If you finish below sea-level this is not a valley (from my reading of the rules). – Contraband

this solution failed in the case of path = "dudu", check my solution – Residue

Answer 2

This problem is about to search how many times did the hiker climb to sea level following his path. try this solution it works for me.

public static int countingValleys(int steps, String path) {
    int s = 0;
    int v = 0;
    for (int i = 0; i < path.length(); i++) {
        if (path.charAt(i) == 'D') {
            s--;
        } else if ((path.charAt(i) == 'U') && (s + 1 == 0)) {
            s++;
            v++;
        } else {
            s++;
        }
    }
    return v;
}

Finer

Answer 3

TypeScript/JavaScript solution:

function countingValleys(steps: number, path: string): number {
  let valleysCount = 0;
  let firstStep = "";
  let stepFromSeaLevel = 0;

  for (let step of path.split("")) {
    firstStep = firstStep || step;
    stepFromSeaLevel += step === "U" ? 1 : -1;

    if (stepFromSeaLevel === 0) {
      valleysCount = valleysCount + (firstStep === "D" ? 1 : 0);
      firstStep = "";
    }
   }

  return valleysCount;
}

Heighten

Answer 4

The key is while going up you have to check for sea level and ignore the downtrend for fast processing.

Here is my simple and precise solution -

static int countingValleys(int n, String s) {

        int valleyCounter = 0, altitude = 0;

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'U') {
                altitude++;
                if (altitude == 0) {
                    valleyCounter++;
                }

            } else {

                altitude--;
            }
        }
        return valleyCounter;
    }

If still not clear and need more explanation you can click here.

Saccharide

Answer 5

/* Counting Valleys */
    public static int countingValleys(int steps, String path) {
        int current_position = 0, vally = 0;
        if(steps >= 2 && steps <= 1000000) {
            int previous_position = 0;
            for(char ch: path.toCharArray()) {
                previous_position = current_position;
                if(ch == 'U') {
                    current_position++;
                } else if(ch == 'D') {
                    current_position--;
                }
                if(current_position == 0 & previous_position < 0 ) {
                    vally ++;
                }
            }
        }
        return vally;
    }

Ashe

Answer 6

C++ optimised solution

   int countingValleys(int steps, string path) {

     int seaLevel = 0, countValley = 0;
     bool isU = false;
     for (char c : path)
     {
        if(c == 'U' || c == 'u')
        {
           isU = true;
           ++seaLevel;
        }            
        else
        {
           isU = false;
           --seaLevel;
        }

        if(seaLevel == 0 && isU)
        {           
           ++countValley;
        }
        
     }

     return countValley;
  }

Residue

Answer 7

This code worked properly for a few test cases but failed some. I'm kinda stuck right now coz the failed test cases are locked in HackerRank. Python 3. I'm new to stackoverflow.

    def countingValleys(steps,path):
     v=0
     level=0
     i=[]
     for k in range(0,steps-1):
        if path[k]=='D':
            level-=1 
        else:
            level+=1 
        if level==0:
            i.append(k+1) 
        else:
            continue
     for j in i:
        if path[j-1]=='D' or path[j]=='D' or path[j+1]=='D': 
            v+=1

     return v        
    s=int(input())
    p=str(input())
    print(countingValleys(s,p))

Escharotic

Answer 8

I first tried solving this one using a stack, however using a basic integer keeping the altitude is much simpler.

public static int countingValleys(int steps, String path) {
    int numberOfValleys = 0;
    int altitude = 0;
    boolean isValleyComplete = false;
    
    for (int i=0; i<steps; i++) {
        char processedStep = path.charAt(i);
        
        if (isValleyComplete && processedStep == 'D') {
            numberOfValleys++;
            isValleyComplete = false;
        }
            
        if (processedStep == 'D') {
            altitude--;
        }
        
        if(processedStep == 'U') {
            altitude++;
        }
        
        if (altitude == 0 && processedStep == 'U') {
            isValleyComplete = true;
            
            if (i == path.length()-1) {
                numberOfValleys++;
            }
        }
    }

    return numberOfValleys;
}

}

Rondelle

Answer 9

public static int countingValleys(int steps, String path) {
// Write your code here
int count=0;
int valleys=0;
for(int i=0;i<path.length();i++){

    if(count==0 & path.charAt(i)=='D')
        valleys+=1;

    if(path.charAt(i)=='U')
        count+=1;

    else
        count-=1;
}

return valleys;
}

Classmate

We have to check and count only when we are at sea level and the next character is 'D'. – Classmate

Answer 10

Below Solution passes all test cases from Hackerrank. The trick is to always check if you are inside a valley and whenever you come out of it increase the count.

 public static int countingValleys(int steps, String path) {
      int step = 0;
      int count = 0;
      boolean isInsideValley = false;
      for (int i = 0; i < path.length(); i++) {
        if (path.charAt(i) == 'U') {
          step++;
        } else if (path.charAt(i) == 'D') {
          step--;
        }
        if (step == -1 && !isInsideValley) {
          isInsideValley = true;
        } else if (step == 0 && isInsideValley) {
          count++;
          isInsideValley = false;
        }
      }
      return count;
  }

Midmost

Answer 11

function countingValleys(steps, path) {
 let status = 0
 let valleyClimbed = 0;
 let prevStatus = 0
    for (let i = 0; i < steps; i++) {
    if (path.charAt(i) === 'U') {
    status++;
    prevStatus = status - 1;
    }else{
    status--;
    prevStatus = status + 1;
    }
    if (status == 0 && prevStatus < 0) {
    valleyClimbed++;
    }
    }
    return valleyClimbed;
    }

Koziel

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Whoop

Answer 12

The Java solution posted above by Dave is not optimized for all input combinations. For an example it doesn't track once a person reach sea level whether the person was on upHill trend or downHill trend.

Posting my solution here, that will take of tracking the uphill/downhill trend before incrementing the counter,

private static int countTheValley(String path) {
    int valleyCounter = -0;
    int seaLevel = 0;
    boolean isDownhill = false;
    for (int i = 0; i < path.length(); i++) {
        // if the hiker is at  sea level,
        // He has to go downhill and that's when he enters a valley
        if (seaLevel == 0 && path.charAt(i) == 'D') {
            isDownhill = true;
        }
        // Caluculate steps from sea level
        if (path.charAt(i) == 'U') {
            seaLevel += 1;
        } else if (path.charAt(i) == 'D') {
            seaLevel -= 1;
        }
        // If the hiker has reached Sea Level
        // And he was downhill that means he's  coming out of a valley
        if (isDownhill && seaLevel == 0) {
            // this is very important
            // if the hike is at sea level reset the downhill to false
            // this ensures our logic is reset for every iteration of uphill/downhill 
            // starting froms sea level
            isDownhill = false;
            valleyCounter += 1;
        }
    }
    return valleyCounter;
}

Sebiferous