Algorithms

HackerRank - Counting Valleys Challenge

One of HackerRank’s Warm-up Challenges in Javascript

Adam

12 Jun 2022

The following solution is written in Javascript.

Problem

An avid hiker keeps meticulous records of their hikes. During the last hike that took exactly steps, for every step it was noted if it was an uphill, U, or a downhill, D step. Hikes always start and end at sea level, and each step up or down represents a unit change in altitude.

Breaking down the challenge into blocks of requirements, we get:

U = A uphill step
D = A downhill step
Each step represents 1 unit
A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
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.

Example


    Steps = 8 path = [D D U U U U D D]

Function Description

The countingValleys function has two parameters:

int steps: the number of steps on the hike
string path: a string describing the path

Returns

int: the umber of valleys traversed

Sample Input


    8
    UDDDUDUU

Sample Output

Explanation

If we represent _ as sea level, a step up as /, and a step down as , the hike can be drawn as:


    _/\      _
       \    /
        \/\/

The hiker enters and leaves one valley.

Goal

Given the sequence of up and down steps during a hike, find and print the number of valleys walked through.

Constraints & Validation

The number of socks n will not be more than 100
The number of a colour ar[i] will not be more than 100


    2 <= steps <= 10^6 (1,000,000)
    path[i] will consist of {UD}

The sockMerchant function expects two arguments, an integer and a sting.


    function countingValleys(steps, path) {

        if (Number.isInteger(steps)
            && steps >= 2 && steps <= Math.pow(10, 6))
        {
            // Loop through path

            // Return number of valleys traversed
        }
    }

Solution

We need to loop through the path string and calculate the number of mountains and valleys traversed. To do this we can increase or decrease the walkers current altitude based on the character being U or D. Each time a walker takes a downhill step when their altitude is at Sea level they enter a valley.


    let alt = 0,
        valleys = 0;

    for (var i = 0; i < path.length; i++) {
      if(str.charAt(i) == 'D')
        if(alt == 0) valleys =+ 1;
        alt -= 1;
      } else {
        alt += 1;
      }
    }

We can now return the number of valleys traversed.

First Attempt Solution


    function countingValleys(steps, path) {
        if (Number.isInteger(steps)
            && steps >= 2 && steps <= Math.pow(10, 6)) {

            let alt = 0,
                valleys = 0;

            for (var i = 0; i < path.length; i++) {
                if(path.charAt(i) == 'D') {
                    if(alt == 0) valleys ++;
                    alt --;
                } else {
                    alt ++;
                }
            }

            return valleys;
        }
    }

Refactored Solution

Although the solution above does work it terminated due to timeout on some of the test cases. This may be caused by the function using the .charAt() method on each loop. I noticed also that I was using path.length in the for loop instead of the steps value.

I refactored the code to test this using a simple array index instead of .charAt()


    function countingValleys(steps, path) {
        if (Number.isInteger(steps)
            && steps >= 2 && steps <= Math.pow(10, 6)) {

            let array = path.split(''),
                alt = 0,
                valleys = 0;

                for (var i = 0; i < steps; i++) {
                    if(array[i] == 'D') {
                        if(alt == 0) valleys ++;
                        alt --;
                    } else {
                        alt ++;
                    }
                }
                return valleys;
            }
        }

The solution above successfully passed each of the test cases demonstrating the importance of using methods only where necessary.