Count Valleys

Approach

We will traverse the string ‘racetrack’ and check 

1. If it is an up step, increase the level by 1.
   1. Check if 'LEVEL' == 0.
   2. If 'LEVEL' == 0, increase the 'NO_OF_VALLEYS' count by 1.
       
2. If it is a down step, reduce the level by 1.

Algorithm

1. Initialize LEVEL = 0, starting at ground level.
    
2. Initialize the count of valleys, i.e., noOfValleys to zero.
    
3. For each step in the racetrack from ‘i = 0’ to ‘i < n’:
   a. If the current step is an up step (represented by 'U'), increase LEVEL by 1.
   b. If the current step is a down step (represented by 'D'), decrease LEVEL by 1.
   c. If the LEVEL becomes zero after taking a step, increment the count of valleys by 1.
    
4. Return the count of valleys.

Dry Run

1. Initialize the level variable to 0 and noOfValleys to 0.
    
2. Loop through the racetrack string “UDDUUDDDUU”
   1. When the current step is 'U':
   2. Increase the level by 1.
   3. If level is now 0, then we have crossed a valley, so increase noOfValleys by 1.
       
3. When the current step is 'D':
   1. Decrease the level by 1.
       
4. After the loop ends, return the noOfValleys.

5. Finally, return the noOfValleys as 2.

Code in C++

#include <iostream>
#include <string>
using namespace std;

// Function to count valleys we have crossed in the racetrack.
int countValleys(int n, string racetrack){
    // Initialize LEVEL = 0, starting at ground level.
    int level = 0;
    // Initialize count of valleys to zero.
    int noOfValleys = 0;

    for (int i = 0; i < n; i++){
        /*
            If the current step is an 
            up step increase the LEVEL by 1.
        */
        if (racetrack[i] == 'U'){
            level++;
            /*
                Check if after an up step our LEVEL = 0, 
                then we know we have crossed a valley so 
                increase the count of valleys by 1.
            */
            if (level == 0){
                noOfValleys++;
            }
        }
        /*
            If the current step is a down step,
            then decrease the LEVEL by 1.
        */
        else{
            level--;
        }
    }
    // return the count of valleys.
    return noOfValleys;
}
int main(){
    int n=11;
    string racetrack="UDDUUDDDUU";
    
    // Calling count valleys function. 
    int noOfValleys = countValleys(n, racetrack);
    cout << noOfValleys << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output
 

Code in Python

# Function to count valleys we have crossed in the racetrack.
def count_valleys(n, racetrack):
    # Initialize LEVEL = 0, starting at ground level.
    level = 0
    
    # Initialize count of valleys to zero.
    no_of_valleys = 0
    
    for i in range(min(n, len(racetrack))):
        # If the current step is an up step,
        # increase the LEVEL by 1.
        if racetrack[i] == 'U':
            level += 1
            # Check if after an up step our LEVEL = 0, 
            # then we know we have crossed a valley so 
            # increase the count of valleys by 1.
            if level == 0:
                no_of_valleys += 1
        # If the current step is a down step, 
        # then decrease the LEVEL by 1.
        else:
            level -= 1
    
    # Return the count of valleys.
    return no_of_valleys

n = 11
racetrack = "UDDUUDDDUU"

# Calling count valleys function. 
no_of_valleys = count_valleys(n, racetrack)

print(no_of_valleys)

You can also try this code with Online Python Compiler

Run Code

Output
 

Complexity

Time Complexity = O(N),
where ‘N’ is the number of steps on the ‘racetrack’.
We traverse the whole string once. So our time complexity is O(N).

Space Complexity = O(1). 
Since we are not using any extra space, space complexity is O(1).

Also see, Rabin Karp Algorithm

Must Read Python String Concatenation

Frequently Asked Questions

How can you compare two strings in c++?

You can use the ‘compare()’ method to compare two strings. We can also use operators ‘==’ and ‘!=’ to compare. We can also use the ‘strcmp()’ function when using string.

How can you find the length of a string in C++?

You can use the ‘length()’ method of the string class in C++ to find the length of a string. We can also use the ‘size()’ and ‘strlen()’ functions.

How to convert a string into an integer using the C++ STL function?

We can use the ‘stoi’ function from C++ STL to convert a string into an integer.

How to convert a string in uppercase or lowercase in C++?

We can convert a string to uppercase or lowercase using the “toupper()” or “tolower()” function in C++.

What is the difference between a character and a string?

A character is a single symbol or letter, while a string is a sequence of characters.

Conclusion

In this blog, we learned about the count valleys problem. We have implemented the problem in C++ and python programming languages.

For more string data structure articles, you can refer following links:

• Catalan Numbers 
• Chinese Remainder theorem
• Count Number of Valid Parenthesis
   

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!