Counting Valleys

user_5362583 0
Viewed 6594

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

counter java
10 Answers

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.

user_1353510

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;
}
user_105249140

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;
}
user_119609770

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.

user_16013090 
/* 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;
    }
user_92937470

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;
  }
user_83926700

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))
user_146005190

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;
}

}

user_61826450 
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;
}
user_78054830

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;
  }
user_85555410
Related